gcd算法：
通过辗转相除求最大公约数
代码语言：javascript复制#include<stdio.h>
int gcd(int a,int b){
return a%b==0?b:gcd(b,a%b);
}
int main(){
printf("%d",gcd(15,18));
return 0;
}扩展gcd算法：
对于不完全为 0 的非负整数 a，b，若gcd(a,b)表示 a，b 的最大公约数，必然存在整数对x，y ，使得 ax by = gcd(a,b)。
设：
ax1 by1=gcd(a,b),
bx2 a%by2=gcd(b,a%b)
因为gcd(a,b)=gcd(b,a%b)，所以
ax1 by1
=bx2 a%by2
=bx2 (a-a/b*b)y2
=ay2 (x2-a/b*y2)b
所以x1=y2,y1=x2-a/b*y2
且if(b==0)不定方程 的一组解为x=1,y=0
因此扩展gcd代码为：
代码语言：javascript复制#include<stdio.h>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1;y=0;return a;}
ll r=exgcd(b,a%b,y,x);
y-=a/b*x;
return r;
}
int main(){
ll a,b,ans,x,y;
scanf("%lld%lld",&a,&b);
ans=exgcd(a,b,x,y);
printf("(%lld) * (%lld) (%lld) * (%lld)=%lld",a,x,b,y,ans);
return 0;
} 
