\[设c=gcd(a,b)，那么a可以表示为mc，b可以表示为nc的形式。然后令a=kb+r，那么我们就\\
只需要证明gcd(b,r)=c即可。{\because}r=a-kb=mc-knc，{\therefore}gcd(b,r)=gcd(nc,mc-knc)\\
=gcd(nc,(m-kn)c)，所以我们只需要证gcd(n,m-kn)=1即可。\\
设n=xd,m-kn=yd，那么m=kn+yd=kxd+yd，进而a=(kx+y)cd,b=xcd\\
，于是gcd(a,b)就可以表示为gcd((kx+y)cd,xcd)=cd，如果要让它等于c，那么d=1，即\\
gcd(n,m-kn)=1。
\]
只需要证明gcd(b,r)=c即可。{\because}r=a-kb=mc-knc，{\therefore}gcd(b,r)=gcd(nc,mc-knc)\\
=gcd(nc,(m-kn)c)，所以我们只需要证gcd(n,m-kn)=1即可。\\
设n=xd,m-kn=yd，那么m=kn+yd=kxd+yd，进而a=(kx+y)cd,b=xcd\\
，于是gcd(a,b)就可以表示为gcd((kx+y)cd,xcd)=cd，如果要让它等于c，那么d=1，即\\
gcd(n,m-kn)=1。
\]
放上模板代码：
int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
//压行之后:
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
原文链接: https://www.cnblogs.com/akura/p/11088720.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/297716
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
