題意：找到一個m，使得m%ai=ri，并且這個m最小

? m = a1*x + r1;

? m = a2*y?+ r2;

可得：a1*x - a2*y = r2 - r1

可得：a1*x?≡ r2-r1(moda2);

r = gcd(a1,a2);

求一次同余線性方程---判定條件 （r2-r1）% ?r==0

解得 x ≡ ?((r2-r1)/r)*x%(a2/r)+a2/r)%(a2/r);

?r1 = a1 * x + r1;

a1 = a1 * a2 / r;再與下一個等式求解

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; typedef __int64 LL; LL x,y; LL ecgcd(LL a,LL b) {if(b == 0) {x = 1,y = 0;return a;}int k = ecgcd(b,a%b);LL t = x;x = y;y = t - a/b*y;return k; } int main() {LL n,a1,a2,r1,r2;while(~scanf("%I64d",&n)){scanf("%I64d%I64d",&a1,&r1);bool flag = false;for(LL i = 2;i <= n;i++){scanf("%I64d%I64d",&a2,&r2);if(flag) continue;LL r = ecgcd(a1,a2);LL R = r2 - r1;if(R%r) {flag = true;continue;}//求解一次同余式的判定LL mod = a2/r;x = (R/r*x%mod+mod) % mod;//解得a1*x = R (mod a2);的一個特解 即最小值r1 = x*a1 + r1;a1 = a1*a2/r;}if(flag) printf("-1\n");else printf("%I64d\n",r1);} }
若還是不明白：點這里? http://hi.baidu.com/buaa_babt/item/5f4c013772c7cbe3e6bb7a2d

總結(jié)

以上是生活随笔為你收集整理的poj-2891(Strange Way to Express Integers)--中国剩余定理扩展欧几里得的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。