2529: 同余方程（拓展欧几里得算法）

解题思路:

一个很简单的思路，令x从1到开始遍历然后a*x对b取余，如果是1的话则输出x，可惜数据规模达到二十亿，只能拿到64的分数。

后来想到了费马小定理，a^(b-1)≡1(mod b)，也就是说x只需要遍历到b-1就可以结束循环了，不过b的取值范围太大了，这个方法并没有什么作用。

后来对 ax≡1(mod b) 做了简单的变化：

 ax≡1(mod b) ->ax-1=b*k，x=(b*k+1)/a，然后判断x是不是整数，这样只需k++即可，最后拿了73分，应该是最后b*k爆long long 范围了，想不到什么好办法了，这道题应该就是只能用拓展欧几里得算法。

这里介绍一下拓展欧几里得算法。

根据裴蜀定理，对于gcd(a,b)=c，一定有（x,y）满足a*x-b*y=c*k，特别的，一定有一组解满足a*x-b*y=c，而拓展欧几里得算法就是来求解这组特别的解（x,y）的。

建议拓展欧几里得不能背模板，每次做的时候现推一遍加深印象，推导过程如下：

设     a*x1+b*y1=gcd(a,b)，b*x2+(a%d)*y2=gcd(b,a%b)

根据欧几里得算法gcd(a,b)==gcd(b,a%b)得 a*x1+b*y1==b*x2+(a%d)*y2

因为(a%b)展开为 a-[a/b]*b

所以得到a*x1+b*y1=b*x2+( a - [a/b] * b ) * y2

展开右边a*x1+b*y1=b*x2 + a*y2 - [a/b]*y2*b

合并同列项 a*x1+b*y1=a*y2 +b (x2-[a/b]*y2 )

所以最后得到：x1=y2,y1=(x2-[a/b]*y2)

ax≡1(mod b) 等价于a*x+b*y=1，就是拓展欧几里得算法求解线性同余的题目。

参考代码:

#include <stdio.h>

int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int n,m;
	n=exgcd(b,a%b,x,y);
	m=x;
	x=y;
	y=m-a/b*y;
	return n;//n 为gcd(a,b)	
}

int main ()
{
	int a,b,x,y;
	scanf("%d %d",&a,&b);
	exgcd(a,b,x,y);
	while(x<0)x+=b;
	printf("%d",x);
	
	return 0;
}

这里的题解是使用c++才通过的，用c会编译错误，现在还没有清楚里面的原理，如果用c的话请使用下面的代码：

#include <stdio.h>
 
int exgcd(int a,int b,int *x,int *y){
    if(b==0){
        *x=1;
        *y=0;
        return a;
    }
    int n,m;
    n=exgcd(b,a%b,x,y);
    m=*x;
    *x=*y;
    *y=m-a/b**y;
    return n;//n 为gcd(a,b)   
}
 
int main ()
{
    int a,b,x,y;
    scanf("%d %d",&a,&b);
    exgcd(a,b,&x,&y);
    while(x<0)x+=b;
    printf("%d",x);
     
    return 0;
}