学习：数学----gcd及扩展gcd
gcd及扩展gcd可以用来求两个数的最大公因数，扩展gcd甚至可以用来求一次不定方程ax+by=c的解
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
1.辗转相除法与gcd
假设有两个数a与b，现在要求a与b的最大公因数，我们可以设
a=b*q+p
如果a是与b的最大公约数是gcd(a,b)，那么b与p的最大公约数也是gcd(a,b)
即
gcd(a,b)=gcd(b,p)=gcd(b,a%b)，然后我们令a=b，b=a%b，然后再进行以上步骤
以此类推，a与b的值会越来越小，直到某一时刻a变成了b的倍数，使得a%b=0，但是后来赋值使得a=b，b=a%b，所以等到b=0的时候，a的值就是原来a与b的最大公约数了。
证明在循环过程中一定存在某一时刻，使得a为b的倍数：
由于当a为正数（负数）时，a%b的值一定是正数（负数），也就是说，当b的值不断减小，最多也就减小到1（-1），而此时a一定是b的倍数。当然，不一定只有当b减小到1（-1）时，才会出现a%b=0，只要当b等于原来a和b最大公约数的时候，就一定会发生a%b=0
总结代码（暂时只写了代码板子，关于gcd和扩展gcd的一切晚点再写）
求：
1.a与b的最大公因数
2.求ax+by=c的某一个解
3.求ax+by=c的最小正整数解（如果不存在则求最靠近0，0的解）
1 #include <iostream>
2 using namespace std; 3 /*1*/long long getGcd(long long _a,long long _b){ 4 if(_b==0) return _a; 5 else return getGcd(_b,_a%_b); 6 } 7 /*2*/long long getExgcd(long long _a,long long _b,long long &_x,long long &_y){ 8 if(_b==0){ 9 _x=1,_y=0; 10 return _a; 11 } 12 long long _gcd=getExgcd(_b,_a%_b,_x,_y); 13 long long _rx=_x; 14 _x=_y; 15 _y=_rx-_a/_b*_y; 16 return _gcd; 17 } 18 /*3*/long long getAnyCalc(long long _a,long long _b,long long _c,long long &_x,long long &_y){ 19 long long _gcd=getExgcd(_a,_b,_x,_y); 20 if(_c%_gcd) return -1; 21 long long _transit=_c/_gcd; 22 _x*=_transit;_y*=_transit; 23 return _gcd; 24 } 25 /*4*/long long getUpCalc(long long _a,long long _b,long long _c,long long &_x,long long &_y){ 26 long long _gcd=getExgcd(_a,_b,_x,_y); 27 if(_c%_gcd) return -1; 28 long long _transit=_c/_gcd; 29 _x*=_transit;_y*=_transit; 30 long long __a=_a,__b=_b; 31 _a/=_gcd;_b/=_gcd; 32 _x=_x%_b<0?_x%_b+(_b<0?-_b:_b):_x%_b; 33 _y=_y%_a<0?_y%_a+(_a<0?-_a:_a):_y%_a; 34 if(_c<0) _y=(_c-__a*_x)/__b; 35 else _x=(_c-__b*_y)/__a; 36 return _gcd; 37 } 38 int main(){ 39 getGcd(long long a,long long b)//1
40 getAnyCalc(long long a,long long b,long long c,long long x,long long y)//2,3
41 getUpCalc(long long a,long long b,long long c,long long x,long long y)//2,4
42 }
求三小问的代码
使用说明：函数getGcd(long long a,long long b)求a与b的最大公约数（需要1号函数）
函数getAnyCalc(long long a,long long b,long long c,long long x,long long y)求ax+by=c的某一个解（不存在解返回-1，存在返回gcd（a,b），解x与y传的是引用）（需要2，3号函数）
函数getUpCalc(long long a,long long b,long long c,long long x,long long y)求ax+by=c的最小非负整数解（不存在解返回-1，存在解且不存在最小非负整数解则得到的解为最靠近（0，0）的解且返回的是gcd（a,b））（需要2，4号函数）
