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

    千次阅读 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)

    展开全文
  • 辗转相除法, 又名欧几里德算法(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。


    展开全文
  • 求两个数的最大公约数的方法:辗转相除法和更相减损术
    1. 辗转相除法 (又称欧几里得算法):使用较大的数除以较小的数得到余数,再用较小的数除以余数,如此往复,直到最后得到的余数为0,那么此时的较大数为原始数的最大公约数。例如求24和16的最大公约数过程如下:(24,16)->(16,8)->(8,0),则8就是24和16的最大公约数。使用C++实现代码如下:
    /**********************************************************
     2. 函数:ComputeGCDivisor1
     3. 描述:计算两个数的最大公约数
     4. 参数:
     5. 返回:
     6. 备注:辗转相除法
    **********************************************************/
    int ComputeGCDivisor1(int a, int b)
    {
    	int c;
    	int GCDivisor;
    
    	if (a<b)
    	{
    		c = a;
    		a = b;
    		b = a;
    	}
    
    	if (b==0)
    	{
    		GCDivisor = a;
    	}
    	else
    	{
    		GCDivisor = ComputeGCDivisor1(b, a % b);
    	}
    
    	return GCDivisor;
    }
    

    此处使用函数递归,即如果a>b,则a和b的最大公约数等于b和a%b的最大公约数。递归的终止条件是b=0,此时的a就是最大公约数。

    1. 更相减损术:老祖宗的智慧结晶,出自《九章算术》。译文:(如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分。例如:24和16的最大公约数:(24,16)->(12,8)->(6,4)->(3,2)->(2,1)->(1,1),到最后数为1 ,但是由于中间约了三次2,所以最大公约数为1*2^3=8。如果遇到两个都是偶数不除以2,而是直接相减,则最后相等的数就是最大公约数。(24,16)->(16,8)->(8,8)。一下为不除以二的方法实现的代码:
    /**********************************************************
     1. 函数:ComputeGCDivisor2
     2. 描述:计算两个数的最大公约数
     3. 参数:
     4. 返回:
     5. 备注:更相减损术
    **********************************************************/
    int ComputeGCDivisor2(int a, int b)
    {
    	while (a!=b)
    	{
    		if (a>b)
    		{
    			a = a - b;
    		}
    		else
    		{
    			b = b - a;
    		}
    	}
    
    	return a;
    }
    
    1. 对辗转相除法的一些粗浅理解:首先是最大公约数的理解,即存在一个数c,能将a分解为x个c和将b分解为y个c,且c其中最大的一个。对于a>b,要寻找将能将a和b同时分解的数,则将a÷b=r…k,如果k为0,则b是最大公约数,如果k不为0,那么此时a已经分解为了r个b加上k,即r*b+k,此时只能将寻找b和k的最大公约数,如果b%k=0,证明b可以分解为整数个k,如果不等于0,则继续做b÷k的运算,直到余数为0。
    展开全文
  • 要求两个正整数的最大公约数有两种方法,辗转相除法和更相减损法。 注:gcd(a,b)代表a和b的最大公约数。 辗转相除法的定义:对于两个正整数a和b,其中a&gt;b,r为a除以b的余数,gcd(a,b) = gcd(b,r); 原理:...

    要求两个正整数的最大公约数有两种方法,辗转相除法和更相减损法。

    注:gcd(a,b)代表a和b的最大公约数。

    辗转相除法的定义:对于两个正整数a和b,其中a>b,r为a除以b的余数,gcd(a,b) = gcd(b,r);

    原理:设a,b的最大公约数为u,a = u · t1; b = u · t2; (t1 , t2 为某个数,满足等式要求,是多少并不重要,一定存在,因为u为a,b的约数),a = nb + r(n为满足等式的某一个数,是多少并不重要,一定存在,因为a>b);r = a - nb = u · t1 - n · u · t2 = u(t1 - n·t2);说明u也是r的约数。

    更相减损法的定义:对于两个正整数a和b,其中a>b,l = a - b,gcd(a,b) = gcd(b,l);

    原理:证明同上,将假设的值带入等式,即可证除l也带有最大公约数u。

    Java实现:

    辗转相除法:

    注意,如果b > a,此算法的第一次循环会将a b交换。

    int num1 = 81;
    int num2 = 27;
    		
    //辗转相除法
    while(num2 != 0){
    	int temp = num2;
    	num2 = num1 % num2;
    	num1 = temp;
    }
    System.out.println("最大公约数为:" + num1);

    更相减损法:

    注意:这个算法一定要保证a>b,否则a - b为负数,会出现bug。

    int num3 = 55;
    int num4 = 25;
    //更相减损法
    while(num3 != num4){
    	int temp = num4;
    	if(num4 > num3){
    	    temp = num4;
    	    num4 = num3;
    	    num3 = temp;
        }
    	num4 = num3 - num4;
    	num3 = temp;
    }
    System.out.println("大公约数为:" + num3);

    优化:

    问题:

    辗转相除法,在数值大的时候,需要进行大数除法,性能较低。

    更相减损法:需要进行较多的循环,极端情况,a=1000,b=1,则需要循环999次。

    这里提出一种结合方法,至于如何提出来的,我也是看别人写的,欣赏一下别人的天才哈。

    • 如果a,b都是偶数,则gcd(a,b) = 2 · gcd(a/2,b/2)
    • 如果a是奇数,b是偶数,则gcd(a,b) = 2 · gcd(a,b/2) 因为其中一个为奇数,那么公约数的因素一定都不包含2
    • 如果a是偶数,b是奇数,则gcd(a,b) = 2 · gcd(a/2,b)
    • 如果a是奇数,b是奇数,则gdc(a,b) = gcd(b,a-b) 奇数相减,一定会出现偶数
            int tt1 = 120;
            int tt2 = 92;
            //辗转相除法和更相减损法的结合
    		//辗转相除法,大数相除性能较低
    		//更相减损法,循环运算次数过多
    		int base = 1;
    		while(tt1 != tt2){
            //保证tt1 是较大的数
    			if(tt1 < tt2){
    				int temp = tt1;
    				tt1 = tt2;
    				tt2 = temp;
    			}
                //双偶
    			if(tt1 % 2 == 0 && tt2 % 2 == 0){
    				tt1 = tt1>>1;
    				tt2 = tt2>>1;
    				base = base * 2;
                //奇偶
    			}else if(tt1 % 2 == 0 && tt2 % 2 != 0){
    				tt1 = tt1>>1;
                //偶奇
    			}else if(tt1 % 2 != 0 && tt2 % 2 == 0){
    				tt2 = tt2>>1;
                //双奇
    			}else if(tt1 % 2 != 0 && tt2 % 2 != 0){
    				int temp = tt2;
    				tt2 = tt1 - tt2;
    				tt1 = temp;
    			}
    		}
    		System.out.println("最大公约数为:" + tt2 * base);

     

    展开全文
  • 题意 传送门 NC 26255 题解 只考虑后两种操作很容易用线段树维护,...根据更相减损术(类似于减法版的辗转相除法),最大公约数有如下性质 gcd(x,y,z… )=gcd(x,y−x,z−y,… )gcd(x,y,z\dots)=gcd(x,y-x,z-y,\dots)g
  • 更相减损法 (又名辗转相减法)4. Stein算法 1. 辗转相除法(又名欧几里德算法) 欧几里得算法,也叫辗转相除,简称 gcd,用于计算两个整数的最大公约数 定义: gcd(a,b) 为整数 a 与 b 的最大公约数 引理:gcd(a,b)...
  • 有一个*龙门粗口*的*这就是祖安人打招呼的方式*博主在以前发了一篇*儒雅随和*的博客,也是讲这个的,虽然写的很*祖安粗口*,但证明还是可堪一看的,(反正是借鉴来的)。 为什么我还会记得多年前的我写博客的亚...
  • 欧几里得算法/辗转相除法/更相减损术 设a0,a1∈Z,a1≠0,按照以下步骤,反复作带余除法:a0=a1q+a2,a2,a3,a4……an−2=an−1q+an,an−1an−1=anq+an+1,an+1=0我们需要证明,以上必为有限步,且(a0,a1)=an设a_{0},a_{...
  • 思路: 除了欧几里得算法求GCD外,还有一种方法可以求GCD,不过速度较慢(最坏会退化为 O(n)O(n)O(n)),那就是九章算术 · 更相减损术:对于 aaa 大于等于 bbb, gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)gcd(a, b) = gcd(b...
  • 更相减损术) 辗转相除法 又名欧几里得算法 ,其原理其实是基于这个定理:\(gcd(a,b)=gcd(b,a\%b)\),详细证明,而任何数与0的最大公约数是它本身 (递归终止条件),所以可以如下递归求出两数最大公因数: \[ f(a,b...
  • 正题 题目链接: ... 大意 ...一个数对(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...
  • 更相减损法和辗转相除法(GCD)求最小公倍数和最大公约数 标签(空格分隔): 算法 算法竞赛 这两种算法平时经常听到,听起来也很装逼,但是我老是忘了他们的原理,今天好好想想,写下来。 相减损法 相减...
  • 本次实验内容为使用以下几种算法1:辗转相除法函数嵌套调用2:辗转相除法函数递归调用3:穷举法(利用数学定义4:更相减损法5:Stein算法函数非递归调用6:Stein算法函数递归调用;求出随机生成的几十组数据(两个一组)...
  • 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,相减损,求其等也。以等数约之。” 翻译成现代语言如下: 第一...
  • 辗转相除法、更相减损法、Stein算法

    万次阅读 多人点赞 2017-07-30 18:42:55
    (1)两者都是求最大公因数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,...
  • 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,相减损,求其等也。以等数约之。” 翻译成现代语言如下: 第一...
  • 本文介绍了用来求最大公约数(GCD)和最小公倍数(LCM)的欧几里得算法(辗转相除法)与更相减损术
  • 辗转相除法的原理

    万次阅读 多人点赞 2019-01-01 23:46:18
    辗转相除法是求最大公约数的一种方法。...这个和更相减损术有着异曲同工之处。 原理: 首先介绍下更相减损术的原理,假设有两个数161和63,我们要求这两个数的最大公因数,不妨假定这个最大公因数为m...
  • 辗转减法求最大公约数

    千次阅读 2019-05-02 17:27:11
    更相减损术) 辗转相减法(求最大公约数),即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。例如 :两个自然数35和14,用大数减去小数,(35,14)->(21,14)->(7,14),此时,7小于14,要做一次交换...
  • 辗转减法

    千次阅读 2020-03-24 16:13:47
    证明方法与辗转相除法类似。 2. 应用 辗转相除法可以用来求若干个形如(pq)ri(\frac pq)^{r_i}(qp​)ri​的数的最大公约数,其中: pq\frac pqqp​不可以再表示为次幂的形式 ppp、qqq、rir_iri​均为正整数 ...
  • 方法(一)更相减损术更相减损术是我国古代数学家求两个正整数最大公约数的算法。我们以求16,12两个数的最大公约数为例加以说明。用两数中较大的数减去较小的数,即16-12=4,用差数4和较小的数12构成一对新数,对这一...
  • 求两个数的最大公约数(辗转减法)

    千次阅读 2019-11-12 17:23:01
    相减损法:也叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求...
  • 文章目录更相减损术 更相减损术 gcd(a,b)=gcd(a,b−a)gcd(a,b)=gcd(a,b-a)gcd(a,b)=gcd(a,b−a) 证明证明证明: 若有gcd(a,b)=dgcd(a,b)=dgcd(a,b)=d,则有a=k1d, b=k2da=k_1d,\ b=k_2da=k1​d, b=k2...
  • 求最大公约数

    2014-12-02 16:20:18
    更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。  《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公...
  • 辗转相减法 辗转相减法也叫更相减损术(尼考曼彻斯法),也是一种简便的求两个数的最大公约数的算法,它的特色是做一系列减法,从而求的最大公约数。比如两个自然数 36 和 27,用大数减去小数得 9 和 27,这时 9 ...
  • 我这证明可能不算严谨吧。。。。 反正OI不需要证明,只需要感性理解。然而我个人觉得感性理解反而比证明重要啊,证明不就是几个式子套来套去,过几天就忘光了。 不妨设a&amp;gt;ba&amp;gt;ba&gt;b,.....
  • 暂时没有证明,大概寒假的时候会补一下证明 完结撒花!我居然在寒假第一天就把这证明补完了... 如果下方的证明有哪里有问题的话,请在下方评论区指出,以提醒作者修改。 定义 \(\phi(n)\)表示在1~n中与n互质的数 ...
  • \(\text{来一波斐波那契公约数的证明}QwQ\) \(\text{已知} \{F_n\} \text{为斐波那契数列,求证:}\) \[\forall\ n,m\in\text{Z}^{+},(F_n,F_m)=F_{(n,m)}\] \(\text{证明:}\) \(\text{令}\) \(n<m\) \(\text{用 }F...
  •  这个版本与版本二都是用更相减损法(),原理中含有递归的思想,所以可以通过递归算法实现,这时算法实现必版本二算法实现简单得多。 算法C实现: /** * @brief get greatest common divisor(gcd) ...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 331
精华内容 132
关键字:

更相减损术证明