gcd（欧几里得算法辗转相除法）：
gcd （ a ， b ）= d ；
即 d = gcd （ a ， b ） = gcd （ b ， a mod b ）；以此式进行递归即可。
之前一直愚蠢地以为辗转相除法输进去时 a 要大于 b ，现在发现事实上如果 a 小于 b，那第一次就会先交换 a 与 b。
#include<stdio.h>
#define ll long long ll gcd(ll a,ll b){
return b==?a:gcd(b,a%b);
} int main(){
ll a,b;
while(scanf("%lld%lld",&a,&b)!=EOF){
printf("%lld\n",gcd(a,b));
// printf("%lld\n",a>b?gcd(a,b):gcd(b,a));
}
return ;
}
在原基础上改成循环之后的GCD：
ll gcd(ll a,ll b){
for(;a>&&b>;a>b?a%=b:b%=a);
return a+b;
}
这个代码是针对非负数范围的，但除此之外我还纠结了很久，在非负数的范围内（long long内）与普通递归的gcd对拍并没有发现问题，一直做题的时候也没有发现有什么问题，但是刷到一题UVA10325，经测试数据中没有给0或负数，但是用这个WA用递归版的AC，并不知道为什么。
所以……还是库函数/递归保平安吧
拓展欧几里得：
当 gcd （ a ， b ）= d 时，求绝对值和最小的 x ， y 使得 x * a + y * b = d ；
d = gcd （ a ， b ） = gcd （ b ， a mod b ）；
设：
x1 * a + y1 * b = d ； ①
x2 * b + y2 * （ a mod b ） = d ； ②
因为 a mod b = a - （ a / b ）* b； ③（除法为整除）
将③代入①整理得：
y2 * a + （ x2 - （ a / b ） * y2 ） * b = d； ④
由①和④整理得：
x1 = y2 ；
y1 = x2 - （ a / b ） * y2；
将此结论代入递归函数既得。
#include<stdio.h>
#define ll long long void gcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b){d=a;x=;y=;}
else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
} int main(){
ll a,b,d,x,y;
while(scanf("%lld%lld",&a,&b)!=EOF){
gcd(a,b,d,x,y);
printf("%lld*%lld+%lld*%lld=%lld\n",a,x,b,y,d);
}
return ;
}
拓展欧几里得求逆元：
当 a 与 b 互素时有 gcd （ a ， b ） = 1 ；
即得： a * x + b * y = 1；
a * x ≡ 1 （ mod b ）；
由于 a 与 b 互素，同余式两边可以同除 a ，得：
1 * x ≡ 1 / a （mod b）；
因此 x 是 a mod b 的逆元；
递归方法计算：
#include<stdio.h>
#define ll long long ll gcd(ll a,ll b,ll &d,ll& x,ll& y){
if(!b){
d=a;
x=;
y=;
return x;
}
else{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
return x;
} int main(){
ll a,b,d,x,y;
while(scanf("%lld%lld",&a,&b)!=EOF){
x=gcd(a,b,d,x,y);
printf("a:%lld->x:%lld\n",a,x);
// printf("a:%lld->x:%lld\nb:%lld->y:%lld\n",a,x,b,y);
}
return ;
}
循环方法计算：
#include<stdio.h>
int main(){
int a,b;
while(scanf("%d%d",&a,&b)!=EOF){
int x=,y=,t;
{
if(a!=&&b!=){
int b0=b,q;
while(a>){
q=a/b0;
t=b0;b0=a%b0;a=t;
t=y;y=x-q*y;x=t;
}
if(x<)x+=b;
}
}
printf("a:%d->x:%d\n",a,x);
}
return ;
}
ll gcd(ll a,ll b){
if(a!=&&b!=){
int b0=b,q,t,x=,y=;
while(a>){
q=a/b0;
t=b0;b0=a%b0;a=t;
t=y;y=x-q*y;x=t;
}
if(x<)x+=b;
}
return x;
}