pku 1891 Strange Way to Express Integers 同余方程组

清疚 2022-08-05 07:50 106阅读 0赞

一般我们求的同余方程组mod 的数是两两互素的，可以直接用孙子定理(中国剩余定理)求解。

然而本题mod的数可能不是互素，所以要转换一下再求。  
x=b1(mod a1); 1)  
x=b2(mod a2); 2)  
a1\*x1+b1=x=b2(mod a2)  
所以a1\*x1+b1=b2(mod a2)  
a1\*x1=(b2-b1)(mod a2)  
我们知道形如AX=B(mod p)的同余式可用扩张欧几里德算法求出一个最小的一个X。所以容易求出x1的值，代入1)式，得出x.  
接着这一步很关键的是将该两个方程合并成一个方程为  
x'==x(mod LCU(a1,a2) );  
然后用该方程与接下来的一个联立，依次求解即可得出结果。

\#include <stdio.h> long long mod(long long a,long long b) \{ return (a % b + b) % b; \} struct triple \{ long long d,x,y; \}; long long Euclid(long long a,long long b) \{ if(b == 0) return a; else return Euclid(b,mod(a,b)); \} triple Extended\_Euclid(long long a,long long b) \{ triple result; if(b == 0) \{ result.d = a; result.x = 1; result.y = 0; \} else \{ triple ee = Extended\_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)\*ee.y; \} return result; \} long long MLES(long long a,long long b,long long n) \{ triple ee = Extended\_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x \* (b / ee.d)),n/ee.d); else return -1; \} long long ExGCD(long long a, long long b, long long& x, long long& y) \{ if(b == 0) \{ x = 1, y = 0; return a; \} long long d = ExGCD(b, a%b, x, y); long long temp = x; x = y; y = temp - a/b\*y; return d; \} long long LCM(long long a, long long b) \{ return a/Euclid(a, b)\*b; \} int main() \{ \_\_int64 k; while(scanf("%I64d", &k) != EOF) \{ \_\_int64 a1, r1, a2, r2; \_\_int64 ret; \_\_int64 i; bool flag = true; scanf("%I64d%I64d", &a1, &r1); for(i = 0; i < k-1; ++i) \{ scanf("%I64d%I64d", &a2, &r2); ret = MLES(a1, r2-r1, a2); if(ret == -1) \{ flag = false; continue; \} r1 = a1\*ret+r1; a1 = LCM(a1, a2); \} if(flag) printf("%I64d/n", r1); else printf("-1/n"); \} return 0; \}