求线性同余方程 求Ax = B(mod C)

// Math // china reminder theorem #include<cstdio> #include<cstdlib> #include<iostream> #define LL long long #define rep(i,a,b) for(int i=a; i<=b; ++i) #define per(i,a,b) for(int i=a; i>=b; --i) #define M 1000000 + 100 using namespace std; LL sp_gcd(LL a,LL b) { LL r; while(b) { r = a % b; a = b; b = r; } return a; } LL ex_gcd(LL a,LL b,LL &x,LL &y) { if(!b){x = 1; y = 0; return a;} else{ LL gcd = ex_gcd(b,a%b,y,x); y-=(a/b)*x; return gcd;} } LL inv(LL a,LL b,LL c) { LL x, y; LL gcd = ex_gcd(a,b,x,y); x = x * (c/gcd); if(c%gcd) return -1; else return (x%(b/gcd)+(b/gcd))%(b/gcd); } LL a[M],m[M]; LL a1, a2, m1, m2; int T; void file() { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); } int main() { //file(); while(scanf("%d",&T)!=EOF && T) { scanf("%lld%lld",&m1,&a1); T--; int flag = 0; while(T--) { scanf("%lld%lld",&m2,&a2); if(flag) continue; LL ni = inv(m2,m1,a1-a2); if(ni == -1) flag = 1; a1 = a2 + m2 * ni; m1 = m1 * m2 / sp_gcd(m1,m2); a1 = (a1 % m1+ m1) % m1; } printf("%lld\n", flag!=1 ? a1 : -1); } }