精华内容
下载资源
问答
  • 欧几里得算法和更相减损术证明

    千次阅读 2019-06-21 10:43:56
    欧几里得算法 gcd(greatest common divisor) 最大公约数,指两个整数所有公共约数中最大的。 首先先上结论,求最大公约数,我们可以通过递归c=a%b,gcd(a,b)=gcd(b,c),c=0时返回b...我们把证明分为两步骤: 1、证...

    欧几里得算法
    gcd(greatest common divisor) 最大公约数,指两个整数所有公共约数中最大的。
    首先先上结论,求最大公约数,我们可以通过递归c=a%b,gcd(a,b)=gcd(b,c),c=0时返回b计算,复杂度是log(n)
    很明显,这个伟大的结论gcd(a,b)=gcd(b,a%b),就是著名的欧几里得公式。
    那么怎么证,其实还挺简单的。我们把证明分为两步骤:

    • 1、证明gcd(a,b)是b,a%b的一个公约数
    • 2、证明这个公约数是最大的。

    1、我们设gcd(a,b)=d,a>b,再令a=k1d,b=k2d.
    我们再设,a=kb+c(也就是a除以b商k余c),那么c就是余数,也就是a%b.
    将上面那个式子移项,得到c=a-k
    b,然后再把a=k1d,b=k2d,这两个式子里的a、b带入式子,得到:
    c=k1d-kk2d,再提取公因数d,得到c=(k1-kk2)d.这样就说明,c(也就是a%b)有d这个约数,因为开始我们设b也有d这个约数,所以gcd(a,b)是b,a%b的一个公约数。
    2、现在知道了它是一个公约数,那么怎么证它是最大的?(其实感性分析,a%b都变小了,公约数不可能更大呀!)
      但是数学是一门严谨的学科,我们要严谨证明。我们知道,c(a%b)=(k1-k
    k2)d,b=k2d,我们只需要证明k1-kk2、k2互质就好了。
    这里可以用到反证法:我们假设k1-k
    k2=qt,k2=pt,并且t>1(也就是那两个不互质)。
    我们将前面那个式子移项,得到k1=qt+kk2,再把这个k1代到最开始的a=k1d,得到a=(qt+kk2)d,再利用乘法分配律,得到:
      a=q
    t
    d+kk2d,这时,我们再把k2=pt带入上式,得到a=qtd+kptd.提取公因数:a=(q+kp)td
      现在,再和b=ptd比较,发现他们的最大公因数变成了t*d和开始矛盾,所以假设不成立,反证成功!
    更相减损术
    不妨设A>B,设A和B的最大公约数为X,所以 A=aX,B=bx,其中a和b都为正整数,且a>b。
    C = A-B,则有:
    C=aX−bX=(a−b)X

    因为a和b均为正整数,所以C也能被X整除,即A、B、C最大公约数均为X
    所以gcd(A,B) = gcd(B,A-B)

    展开全文
  • 更相减损术) 辗转相除法 又名欧几里得算法 ,其原理其实是基于这个定理:\(gcd(a,b)=gcd(b,a\%b)\),详细证明,而任何数与0的最大公约数是它本身 (递归终止条件),所以可以如下递归求出两数最大公因数: \[ f(a,b...

    求最大公因数(辗转相除法&更相减损术)

    辗转相除法

    又名欧几里得算法 ,其原理其实是基于这个定理:\(gcd(a,b)=gcd(b,a\%b)\)详细证明,而任何数与0的最大公约数是它本身 (递归终止条件),所以可以如下递归求出两数最大公因数:
    \[ f(a,b)=\left\{ \begin{array}{lll} b \qquad a\%b=0\\ f(b,a\%b) \end{array} \right. \]
    递归实现(C++):

    int f(int a, int b){
        return (b==0)?(a):f(b,a%b);
    }

    无需判断a,b的大小关系

    更相减损术

    出自《九章算术》,其依据原理:两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数,同理,所以可以如下递归求出两数最大公因数:
    \[ f(a,b)=\left\{ \begin{array}{lll} a \qquad a=b\\ f(b,a-b) \end{array} \right. \]
    递归实现(C++):

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int f(int a, int b){//a>b
        int r=a-b;
        if(r==0)    return b;
        if(r>b) return f(r,b);
        else    return f(b,r);
    }
    int main(){
        int a,b;
        cin>>a>>b;
        if(a<b)
            swap(a,b);
        cout<<f(a,b);
        return 0;
    }

    本文采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载,请注明出处: 转载自:Santiego的博客

    转载于:https://www.cnblogs.com/santiego/p/9568208.html

    展开全文
  • 辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因数的算法。 原理 ...辗转相除法即是要证明gcd(a,b)=gcd(b,r)。 第一步:令c=gcd(a,b),则设a=mc,b=nc 第二步:

    辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因数的算法。

    原理
    设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商,即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
    第一步:令c=gcd(a,b),则设a=mc,b=nc
    第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
    第三步:根据第二步结果可知c也是r的因数
    第四步:可以断定m-kn与n互质【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数成为cd,而非c,与前面结论矛盾】
    从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。
    证毕。
    
    更相减损术
    更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。
    《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
    翻译成现代语言如下:
    第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
    第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
    则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
    其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。
    
    2实例
    例1、用更相减损术求98与63的最大公约数。
    解:由于63不是偶数,把98和63以大数减小数,并辗转相减:
    98-63=35
    63-35=28
    35-28=7
    28-7=21
    21-7=14
    14-7=7
    所以,98和63的最大公约数等于7。
    例2、用更相减损术求260和104的最大公约数。
    解:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26。
    此时65是奇数而26不是奇数,故把65和26辗转相减:
    65-26=39
    39-26=13
    26-13=13
    所以,260与104的最大公约数等于13乘以第一步中约掉的两个2,即13*2*2=52。


    展开全文
  • 正题 题目链接: ... 大意 ...一个数对(a,b),每次可以变为(a+b,b)或(a,a+b)。然后要求一个数对中有n求从(1,1)变成这个数对的...相减损法是gcd(a,b)=gcd(a,b-a)/gcd(a-b,b) 证明: a∣d,b∣da∣d,b∣da\mid d...

    正题

    题目链接:
    https://www.luogu.org/problemnew/show/P2090


    大意

    一个数对(a,b),每次可以变为(a+b,b)或(a,a+b)。然后要求一个数对中有n求从(1,1)变成这个数对的最小次数。


    解题思路

    更相减损法是gcd(a,b)=gcd(a,b-a)/gcd(a-b,b)
    证明:

    ad,bd

    所以
    (ab)d

    我们设a=bb=ab
    那么
    gcd(a,b)=gcd(a,a+b)

    没错,是不是有些眼熟。更相减损术的次数就是到达一个数对需要的最少次数。
    我们就可以枚举一个x,然后求数对(n,x)的最小次数。

    但是!

    会超时。然后我们就可以用欧几里得算法
    我们可以发现(b,ab)进行x次就是(b,abx)。所以我们可以发现如果要从
    (b,abx)变到(b,a%b)x需要等于a/b,所以我们可以用一个wgcd(x,y)表示变到数对(x,y)需要的次数,当b=1时我们只可以将1不断累加到a上面所以需要的次数就是a1
    返回

    wgcd(x,y){x1      (y=1)inf      (y=0)a/b+wgcd(y,x%y)      (y>1)


    代码

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,mins;
    int gcd(int x,int y)//wGCD
    {
        if (y==1) return x-1;
        if (!y) return 1e9;
        return x/y+gcd(y,x%y);
    }
    int main()
    {
        mins=2147483647;
        scanf("%d",&n);
        for (int i=1;i<=(n+1)/2;i++)//枚举(n,i)
            mins=min(mins,gcd(n,i));
        printf("%d",mins);
    }
    展开全文
  • 有一个*龙门粗口*的*这就是祖安人打招呼的方式*博主在以前发了一篇*儒雅随和*的博客,也是讲这个的,虽然写的很*祖安粗口*,但证明还是可堪一看的,(反正是借鉴来的)。 为什么我还会记得多年前的我写博客的亚...
  • 【没啥子】OI小细节

    2019-04-14 20:04:00
    2019,3.09: 于此日开始记录一些OI小细节, 今天发现了memset的惊天内幕,他的复杂度是根据定的数组长度L来定的 所以为\(o(L)\),一定要小心哦...证明:同更相减损术。 小性质2:sqrt满足多次开根等于1/0 证明:显然...
  • 8/13训练日记

    2019-08-14 00:09:31
    今天看到了最大公约数的九章算术——更相减损术,就是一般来说的辗转相减法,还有欧几里得算法,就是辗转相除法。在做题的时候可以不背过这些最大公约数和最小公倍数的缩写(gcd()、lcm()),但是看这本书必须背过,...
  • \(Description:\) 写高精的\(gcd(a,b)\) \(Sample\) \(Input\): ...一开始单纯的以为可以直接高精过,用更相减损术做gcd,结果wei大了。 敲了一个压了八位的高精,又wei了。 我开始思考。。。 事实证明我得写正解...
  • 题意 求\(\gcd(a, b)\),其中\(a,b\leq10^{10000}\) 题解 使用\(\text{Stein}\)算法,其原理是不断筛除因子\(2\)然后使用更...再证明更相减损术,即\(\gcd(a,b)=gcd(a-b,b)\): 假设\(d=\gcd(a,b)\),则\(a=pd,b...
  • 首先三个操作可以理解为更相减损术或者辗转相除法(待证明),所以就是求区间gcd。 这题的问题在线段树维护gcd只能支持修改成一个数,不支持加一个数。 套路:gcd(a,b,c,d,e)=gcd(a-b,b-c,c-d,d-e,e),也就是所有...
  • 题意 给定一个序列有两种操作,一种是求一段区间的gcd,另一种是给一段区间加上一个...根据更相减损术可知gcd(x,y)=gcd(x,y-x),那么易得对于三个数gcd(x,y,z)=gcd(x,y-x,z-y); 用数学归纳法容易证明该性质堆任意...
  • Power Tower

    2019-11-23 20:12:58
    一、题目 点此看题 二、解法 好像是一个欧拉降幂版题,但仔细想想时间复杂度是O(n2)O(n^2)O(n2)。...证明可以考虑更相减损术,gcd⁡(i,n)=gcd⁡(n−i,n)\gcd(i,n)=\gcd(n-i,n)gcd(i,n)=gcd(n−i,n),所以i...
  • 斐波那契数列,是一个经典的递推数列。在实际生活中有很多应用。 我们一般都知道它的递推公式: F[1]=1,F[2]=1,...,F[n]=F[n-1]+Fn-2 或者说通项公式......(这...证明: 根据更相减损术 \(gcd(F_{i+1},F_i)\) \(=...
  • 最大公因数第一次出现记得是在小学的时候,那时老师要求用短除法(实质就是质因子分解)来解决,但是,到高中貌似是必修三的时候才知道,有“辗转相除法”和“更相减损术”等方法能够更快的求出两个数的最大公因数。...
  • gcd以及exgcd入门讲解

    2018-07-28 00:01:00
    gcd就是最大公约数,gcd(x, y)一般用(x, y)表示。与此相对的是lcm,最小公倍数,lcm(x, y)一般用[x, y]表示。 ...至于gcd的求法,想必各位在高中都学过辗转相除法和更相减损,这里只讲辗...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

更相减损术证明