Modular Inverse（模线性方程）

2019-04-13 16:55发布

站内文章 / 模拟电子
15980 0 1093
http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=89#problem/F 求解 ax≡1 (mod m). 原式相当于 ax(mod m) = 1(mod m),那么 ax-1 是m的倍数。 设ax-1 = my ——> ax - my = 1。 该式有解的前提是 1 是 a和m的最大公约数的倍数，因此 a 和 m 互质，方程有唯一解。 然后再用扩展欧几里得。注意m等于1的时候x的最小值是1。 #include #include #include using namespace std; int gcd(int a, int b) { if(b == 0) return a; return gcd(b,a%b); } int extend_gcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; y = 0; return a; } int r = extend_gcd(b,a%b,y,x); y -= x*(a/b); return r; } int main() { int test; int a,m; scanf("%d",&test); while(test--) { scanf("%d %d",&a,&m); if(m == 1) { printf("1 "); continue; } if(gcd(a,m) != 1) { printf("Not Exist "); continue; } int x,y; extend_gcd(a,m,x,y); if(x < 0) x += m; printf("%d ",x); } return 0; }


热门文章