hdu1211（模的逆元、扩展欧几里得）

2019-04-13 16:55发布

站内文章 / 模拟电子
9573 0 1774
eg：解二元不定方程ax+by+c=0
 1）当a=0或b=0时，方程的解确定 2）c不是gcd的倍数时，方程无解 故只考虑ab！=0且c|gcd(a,b)的情况
1、扩展欧几里得算法      找出一对整数(x,y)，使得ax+by=gcd(a,b)。 例如，gcd(6,15)=3，6*3-15*1=3，其中x=3，y=-1。 这个方程还有其他解，如x=-2，y=1。
2、公式推导 已知a,b的一组解x，y使得 ax+by=gcd(a,b) 根据gcd，下一步a'=b,b'=a%b 求得a'x'+b'y'=gcd(a',b')
即bx'+(a%b)y'=gcd(a'b')=gcd(a,b) bx'+(a-⌊a/b⌋*b)y'=gcd(a,b)，ay'+b(x'-⌊a/b⌋y')=gcd(a,b)展开得对比原式ax+by=gcd(a,b) 得x=y'，y=x'-⌊a/b⌋y'
上述过程翻译成c程序得： int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; }
更加简练的写法： void gcd(int a, int b, int& d, int& x, int& y) { if(!b){ d = a; x = 1; y = 0; } else{ gcd(b, a%b, d, y, x); y -= x*(a/b); } }
3、扩展欧几里德算法求模的逆元 ax=1modb 等价于ax-by=1; 则用扩展欧几里得算法gcd(a,b)=1为方程的解
代码如下： !!!要注意的就是exgcd求出来的d可能是负数，题目要求的是正数 #include int exgcd(int a,int b,int &x,int &y) { if(b==0){ x=1;y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; } int pow_mod(int a,int b,int c) { int t=a%c, ans=1%c; while(b){ if(b&1){ ans=ans*t%c; b--; } b=b>>1; t=t*t%c; } return ans; } int decrypt(int c,int d,int n) { int m=pow_mod(c,d,n); return m; } int main() { //freopen("in.txt","r",stdin); int p, q, e, d, f ,l, n, x, y, c; while(scanf("%d %d %d %d",&p,&q,&e,&l)!=EOF){ n=p*q; f=(p-1)*(q-1); exgcd(e,f,x,y); d=((x%f)+f)%f;//d是正数 for(int i=0;i