题目传送门:http://poj.org/problem?id=2891
这个东西,不保证互质,所以中国剩余定理上不了
于是就得合并方程:
把\(\left\{ \begin{array}{l}
x \equiv {a_1}(Mod{\rm{ }}{b_1})\\
x \equiv {a_2}(Mod{\rm{ }}{b_2})
\end{array} \right.\)
替换成\(x \equiv {a_1} + A \cdot {b_1}(Mod{\rm{ }}\frac{{{b_1} \cdot {b_2}}}{{GCD({b_1},{b_2})}})\)
其中A为\(A \cdot {b_1} – B \cdot {b_2} = {a_2} – {a_1}\)的最小非负整数解
至于推导过程嘛,就自己推一推咯,不想写latex了,太费时间
#include<iostream> #include<cstdio> #define LL long long using namespace std; inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();} return ret*f; } LL GCD(LL a,LL b){return b?GCD(b,a%b):a;} LL EX_GCD(LL a, LL b, LL &x, LL &y){ if (!b) {x=1;y=0;} else {EX_GCD(b,a%b,y,x);y-=a/b*x;} } inline LL EX_GCD(LL a, LL b, LL pur){ LL ret,tmp; EX_GCD(a,b,ret,tmp); return ((ret*pur)%b + b) % b; } int main(){ int n; while (~scanf("%d",&n)) { LL b1=read(),a1=read(),a2,b2,tag=0,A,tmp,gcd; for (int i=1;i<n;i++) { b2 = read(); a2 = read(); gcd = GCD(b1,b2); if (!tag) { if ((a2-a1)%gcd) tag = 1, printf("-1\n"); else { A = EX_GCD(b1/gcd,b2/gcd,(a2-a1)/gcd); a1 = a1 + (A*b1); b1 = b1/gcd*b2; a1 %= b1; } } } if (!tag) printf("%lld\n",((a1%b1)+b1)%b1); } return 0; }
另外,这个题,貌似会爆long long,不过只要你的代码跟我的差不多,就能过QAQ
不得不说,这个题目真的是出得辣鸡,数据范围都没给全………