数论--gcd

1. 辗转相除法：

原理：

$$\gcd (x,y)=\gcd (y,x\mathrm{mod}y)$$

证明：

设 $z$ 为 $x,y$ 的最大公约数。

有 $z|x\text{ , }z|y$ ，则 $z|(y-x)$ 。

所以：

$$\gcd (x,y)=\gcd (x,x-k\times y)=\gcd (y,x\mathrm{mod}y)(k\times y\le x<(k+1)\times y)$$

当 $x<y$ 时：

$$x\mathrm{mod}y=x$$

所以：

$$\gcd (x,y)=\gcd (y,x)$$

当 $y<x$ 时：

$$\gcd (x,y)=\gcd (y,x\mathrm{mod}y)$$

当 $y==0$ 时，答案为 $x$ 。

int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}

2. 二进制算法：

通过不断筛去因子 $2$ 来提高效率。

若 $x=y$ ，则 $\gcd (x,y)=x$ ，否则：

• 若 $x,y$ 为偶数，则 $\gcd (x,y)=2\times \gcd (x/2,y/2)$

• 若 $x$ 为偶数， $y$ 不为偶数，则 $\gcd (x,y)=\gcd (x/2,y)$

• 若 $y$ 为偶数， $x$ 不为偶数，则 $\gcd (x,y)=\gcd (x/2,y)$

• 若 $x,y$ 均不为偶数，则 $\gcd (x,y)=\gcd (x-y,y)$

int GCD(int x,int y)
{
	if(x==0)return y;
	if(y==0)return x;
	int i=0,j=0;
	for(; (x&1)==0; i++)x>>=1;
	for(; (y&1)==0; j++)y>>=1;
	i=min(i,j);
	while(1)
	{
		if(x<y)swap(x,y);
		if(0==(x-=y))return y<<i;
		while((x&1)==0)x>>=1;
	}
}