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\n"); continue; } if(gcd(a,m) != 1) { printf("Not Exist\n"); continue; } int x,y; extend_gcd(a,m,x,y); if(x < 0) x += m; printf("%d\n",x); } return 0; }