poj—2891Strange Way to Express Integers-中国剩余定理-非互质版

题目大意:选择a1,a2....ak,对于某个整数m分别对ai求余对应整数ri,现在已知a1,a2,....ak,以及整数对(ai,ri),求非负整数m的值,若有多个m，输出最小的一个。

解题思路: 容易列出方程 m % ai = ri,可以转化为同余方程 m ≡ ri (mod ai),接着套用求解多元线性同余方程的模版即可。 中国剩余定理： 互质版 例1：一个数被3除余1，被4除余2，被5除余4，这个数最小是几？ 题中3、4、5三个数两两互质。 则〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60。 为了使20被3除余1，用20×2=40； 使15被4除余1，用15×3=45； 使12被5除余1，用12×3=36。 然后，40×1＋45×2＋36×4=274，  因为，274>60，所以，274－60×4=34，就是所求的数。    例2：一个数被3除余2，被7除余4，被8除余5，这个数最小是几？ 题中3、7、8三个数两两互质。 则〔7，8〕=56；〔3，8〕=24；〔3，7〕=21；〔3，7，8〕=168。 为了使56被3除余1，用56×2=112； 使24被7除余1，用24×5=120。 使21被8除余1，用21×5=105； 然后，112×2＋120×4＋105×5=1229，  因为，1229>168，所以，1229－168×7=53，就是所求的数。    例3：一个数除以5余4，除以8余3，除以11余2，求满足条件的最小的自然数。 题中5、8、11三个数两两互质。 则〔8，11〕=88；〔5，11〕=55；〔5，8〕=40；〔5，8，11〕=440。 为了使88被5除余1，用88×2=176； 使55被8除余1，用55×7=385； 使40被11除余1，用40×8=320。 然后，176×4＋385×3＋320×2=2499，  因为，2499>440，所以，2499－440×5=299，就是所求的数。 ps：

中国剩余定理非互质版

    中国剩余定理求解同余方程要求模数两两互质，在非互质的时候其实也可以计算，这里采用的是合并方程的思想。下面是详细推导。

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; __int64 a[100000],b[1000000]; void ex_gcd(__int64 a,__int64 b,__int64 &d,__int64 &k1,__int64 &k2) { if(!b) k1=1,k2=0,d=a; else { ex_gcd(b,a%b,d,k2,k1); k2-=k1*(a/b); } } __int64 china(__int64 *a,__int64 *b,__int64 n) //互质版 { __int64 i; __int64 d,k1,k2,x=0,m,k=1; for(i=0;i<n;i++) k*=a[i]; for(i=0;i<n;i++) { m=k/a[i]; ex_gcd(a[i],m,d,k1,k2); x=(x+k2*m*b[i])%k; } return x>0?x:x+k; } __int64 ex_china(__int64 *a,__int64 *b,__int64 n) //非互质版 { __int64 x=a[0],y=b[0],k1,k2,d; for(int i=1;i<n;i++) { ex_gcd(x,a[i],d,k1,k2); if((b[i]-y)%d) return -1; k1=(b[i]-y)/d*k1%(a[i]/d); y+=k1*x; x=x/d*a[i]; y%=x; } return y>0?y:y+x; } int main() { __int64 n,i; while(~scanf("%I64d",&n)) { for(i=0;i<n;i++) scanf("%I64d%I64d",&a[i],&b[i]); printf("%I64d\n",ex_china(a,b,n)); } return 0; }