##Update 2010-4-16
這里稍微證明一下:
給定方程
x = c1 (mod b1) ……………………(1)
x = c2(mod b2) ………………………(2)
(b1,b2)可以不為1
于是通過(guò)取mod 定義，我們得到
x = k1 * b1 + c1………………(3)
(3) 帶入(2)
k1 * b1 + c1 = c2 (mod b2)…………(4)
化簡(jiǎn)
k1 * b1 = c2 - c1 (mod b2)…………(5)
于是可以解得到
令G = gcd(b1,b2),C = c2 - c1 (mod b2)
那么由(5)得到
k1 * b1 = W * b2 + C
---->>>>>
k1 * b1 / G = W * b2 / G + C / G
令C' = C/G
k1 * b1 / G = W * b2 / G + C '
k1 * b1 / G = C' (mod b2 / G)
--->
k1 = K (mod b2/G)………………(6)
那么有
k1 = k' * b2/G + K………………(7)
(7)帶入(3)
x = k' * b2 * b1/G + K * b1 + c1………………(8)
x = K*b1 + c1 (mod b1 * b2/G)
通過(guò)合并方程的方法成功AC下面此題
題目地址
#include<iostream>
#include<cmath>
using namespace std;
//x = c1 ( mod b1)
//x = c2 ( mod b2)
//若可以可并，則返回合并結(jié)果，否則返回-1
可以處理gcd(b1,b2)!=1的情況
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ext_gcd(int a,int b,int& x,int& y){
int t,ret;
if (!b){
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
//求a對(duì)n的乘法逆元，若不存在返回-1
int Invmod(int a,int n){
int x,y;
if (ext_gcd(a,n,x,y)!=1)return -1;
return (x%n+n)%n;
}
int mergef(int b1,int c1,int b2,int c2,int &b,int &c)
{
int tb1=b1,tb2=b2;
c=((c2-c1)%b2+b2)%b2;
int G=gcd(b1,b2);
if(c%G)return 0;
c/=G;
b1/=G;
b2/=G;
c*=Invmod(b1,b2);
c%=b2;
c*=tb1;
c+=c1;
b=tb1*tb2/G;
c%=b;
return 1;
}
int main()
{
int b1,b2,c1,c2,b,c;
while(cin>>b1>>c1>>b2>>c2)
{
if(mergef(b1,c1,b2,c2,b,c))
cout<<"X = "<<c<<' '<<"(mod "<<b<<')'<<endl;
}
return 0;
}擴(kuò)充了算法導(dǎo)論中中國(guó)剩余定理部分的內(nèi)容，使得它可以處理更一般的情況了，這個(gè)模板具有通用性。
轉(zhuǎn)自：
http://hi.baidu.com/aekdycoin/blog/item/71d7a842b93f611b73f05da4.html順便提一下，除了整理模板之外，要開(kāi)始網(wǎng)絡(luò)流部分的強(qiáng)化訓(xùn)練了，強(qiáng)化構(gòu)圖能力。