欧几里得(GCD)及拓展欧几里得(ExGCD)

欧几里得(辗转相除法)

证明cpp

略，后面补

代码实现

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

二进制优化

inline int gcd(int x,int y)//欧几里得二进制算法优化
{
    int i,j;
    if(x==0)return y;
    if(y==0)return x;
    for(i=0;0==(x&1);i++)x>>=1;//去掉所有的2
    for(j=0;0==(y&1);j++)y>>=1;//去掉所有的2
    if(j<i)i=j;
    while(1)
    {
        if(x<y)x^=y,y^=x,x^=y;//若x<y交换x,y
        if(0==(x-=y))return y<<i;
        //若x==y,gcd==x==y(就是在辗转减，while(1)控制）
        while(0==(x&1))x>>=1;//去掉所有的2
    }
}

拓展欧几里得

解决问题：求解 $ax+by\equiv gcd(a,b) $ 的一组特解

证明

int ExGcd(int a,int b,int& x,int& y)
{
    if (b==0) {
    	x=1;
    	y=0;
    	return a;
	}
	int ans=ExGcd(b,a%b,x,y);	//先计算底层x y 
	int temp=y;
	y=x-(a/b)*y;
	x=temp;
	return ans;
}