来来来 让我装一波。。。。剩余定理、、搬运链接http://blog.csdn.net/d_x_d/article/details/48466957 其实挺简单的。。注意乘积还有和用long long就好了
```c
#include<stdio.h>

int main()
{
int n,a,b;
scanf("%d",&n);
scanf("%d%d",&a,&b);
long long ans = b, c = a;
int i;
for(i=2; i <= n; i++)
{
scanf("%d%d",&a,&b);
while(ans % a != b)
ans += c;
c *= a;
}
printf("%lld\n",ans);
return 0;
}
```

#1 Accepted 1ms 332.0KiB
#2 Accepted 1ms 336.0KiB
#3 Accepted 1ms 480.0KiB
#4 Accepted 1ms 460.0KiB
#5 Accepted 1ms 332.0KiB
#6 Accepted 1ms 328.0KiB
#7 Accepted 1ms 332.0KiB
#8 Accepted 1ms 504.0KiB
#9 Accepted 1ms 328.0KiB
#10 Accepted 1ms 328.0KiB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll M = 1, p[105], a[105], ans;
void exgcd(ll a, ll b, ll &x, ll &y){
if(b == 0) x = 1, y = 0;
else {
exgcd(b,a%b,y,x);
y -= (a/b) * x;
}
}
ll inv(ll a, ll b){
ll x, y;
exgcd(a,b,x,y);
return (x%b+b)%b;
}
int main(){
ll i, j, n, m;
scanf("%lld", &n);
for(i = 1; i <= n; i++){
scanf("%lld %lld", &p[i], &a[i]);
M *= p[i];
}
for(i = 1; i <= n; i++) p[i] = M / p[i];
for(i = 1; i <= n; i++){
ans += inv(p[i], M/p[i]) * a[i] * p[i] % M;
}
ans %= M;
printf("%lld",ans);
return 0;
}

这是一道中国剩余定理（孙子定理）的裸模板题
加一个犇犇的空间（多亏他的讲解）：

下面来简单解释下中国剩余定理（孙子定理）：
1.定义：若m _1
1
​ ,m _2
2
​ \cdots⋯ m n
n
​ 是两两互质的正整数，M= \prod{i=1}^n{m_i}∏
i=1
n
​ m
i
​ ，M _i
i
​ =M/m _i
i
​ ,t _i
i
​ 是线性同余方程M _i
i
​ t _i
i
​ ≡1（mod m _i
i
​ ）的一个解。对于任意的n个整数a _1
1
​ ，a _2
2
​ \cdots⋯ a _n
n
​ ，则同余方程组：
\begin{cases}x≡a_1(mod)m_1\x≡a_2(mod)m_2\ \cdots \cdots\x≡a_n(mod)m_n\\end{cases}
⎩
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎧
​

x≡a
1
​ (mod)m
1
​

x≡a
2
​ (mod)m
2
​

⋯⋯
x≡a
n
​ (mod)m
n
​

​

有整数解，方程组的解为x=a _1
1
​ M _1
1
​ t _1
1
​ +a _2
2
​ M _2
2
​ t _2
2
​ + \cdots⋯ +a _n
n
​ M _n
n
​ t _n
n
​ .并且在%M意义下有唯一解。
2.证明：因为M _i
i
​ =M/m _i
i
​ 是除m _i
i
​ 之外所有模数的倍数，所以 \forall∀ （任意）k \not≠= i，a _i
i
​ M _i
i
​ t _i
i
​ ≡0(mod m _k
k
​ ).又因为a _i
i
​ M _i
i
​ t _i
i
​ ≡a _i
i
​ (mod m i
i
​ )，
所以代入x=
\sum{i=1}^{n}{a_iM_it_i}
i=1
∑
n
​ a
i
​ M
i
​ t
i
​

4.结论：中国剩余定理给出了模数两两互质的线性同余方程组的一个特殊解。方程组的通解可以表示为x+kM（k∈Z）。有些题目要求我们求出最小的非负整数解，只需把x对M取模，并让x落在0~M-1的范围内即可。
4注： \prod_{i=1}^n{m_i}∏
i=1
n
​ m
i
​ 表示m _i
i
​ 从1一直累乘到n.
5提示：看不懂也没事，多理解理解 （相当于没说） ╰(￣▽￣)╭
6算法实现：

int intchina(int r)
{
int Mi,x,y,d,ans=0;M=1;
for(int i=1;i<=r;i++) M*=m[i];
for(int i=1;i<=r;i++){
M[i]=M/m[i];
exgcd(Mi,m[i],d,x,y);
ans=(ans+Mi*x*a[i])%M;
}
return (ans+M)%M;
}
思路点拨：中国剩余定理的模板题（没什么可以点拨的，就一裸的板子题）
code
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll a[11],b[11],n,mod=1,ans=0;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(b==0) d=a,x=1,y=0;
else{
exgcd(b,a%b,d,x,y);
ll temp=x;x=y;y=temp-a/b*y;
}
}
void intchina()
{
ll each,x,y,d;
for(ll i=1;i<=n;i++){
each=mod/a[i];
exgcd(each,a[i],d,x,y);
ans=((ans+each*x*b[i])%mod+mod)%mod;
}
printf("%lld\n",ans);
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld%lld",&a[i],&b[i]);
mod*=a[i];
}
intchina();
return 0;
}

我真的看不懂那个超短的代码，弱啊。。。

#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
int N;
LL A[15], B[15], M=1;
/*
int QUICKPOW (int a, int k, int m) {
    
    int ans=1;
    while(k>0) {
        if (k&1) ans=ans*a%m;
        a=a*a%m;
        k>>=1;
    }
    return ans%m;
    
}
*/
LL EXGCD (LL a, LL b, LL &x, LL &y) {
    
    if (!b) {
        x=1;
        y=0;
        return a;   
    }
    LL g=EXGCD(b, a%b, x, y);
    LL t=x;
    x=y;
    y=t-a/b*y;
    return g;
    
}
LL IE (LL a, LL m) {
    
    //return QUICKPOW(a, m-2, m);
    LL x, y;
    EXGCD(a, m ,x, y);
    return (x%m+m)%m;
    
}
int main () {
    
    cin >> N;
    LL ans=0;
    for(int i=1; i<=N; i++) {
        cin >> B[i] >> A[i];    
        M*=B[i];
    }
    for(int i=1; i<=N; i++) {
        LL x=M/B[i], e=IE(x, B[i]);
        ans=ans+x*e*A[i]%M;
    }
    cout << ans%M;
    return 0;
    
}

裸的中国剩余定理为什么AC率才24%。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
long long a,b;

int main()
{
    scanf("%d",&n);
    long long cur = 0;
    long long t = 1;
    while(n--)
    {
        long long c,d; 
        scanf("%lld%lld",&c,&d);
        while(cur % c != d % c) 
            cur += t;
        t *= c;
    }
    printf("%lld",cur);
    return 0;
}
     

##其实说白了就是：**中国剩余定理**
数学问题，希望好好思考。
特别注意，本代码使用了输入输出优化。
C++如下：

#include<cstdio>
#define R register
#define ll long long
int s()
{
R char ch=getchar();
R int x=ch-'0';
for(;(ch=getchar())>='0'&&ch<='9';)
x=x*10+ch-'0';
return x;
}
int w(R ll r)
{
if(r>9)
w(r/10);
putchar(r%10+'0');
}
int main()
{
R int n,a,b;
n=s();a=s();b=s();
long long int gcd=a,ans=b;
for(R int i=2;i<=n;i++)
{
a=s();b=s();
while(ans%a!=b)
ans+=gcd;
gcd*=a;
}
w(ans);
return 0;
}

这个程序的运行结果就是：

编译成功

foo.cpp: In function 'int w(long long int)':
foo.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
测试数据 #0: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 540 KiB, score = 10
Accepted, time = 0 ms, mem = 544 KiB, score = 100
希望对大家有所帮助，接下来再接再厉！

孙子

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6071521.html

扩展欧几里得 合并同余式
```
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
if (!b) {
gcd=a; x=1; y=0;
} else {
exgcd(b,a%b,gcd,y,x); y-=x*(a/b);
}
}

int main()
{
ll n,a[20],b[20]; cin>>n;
for (ll i=1;i<=n;i++)
{
cin>>b[i]>>a[i];
}
for (ll i=1;i<n;i++)
{
ll gcd,x,y;
exgcd(b[i],-b[i+1],gcd,x,y);
x*=(a[i+1]-a[i])/gcd;
a[i+1]=a[i]+x*b[i];
b[i+1]*=b[i];
a[i+1]%=b[i+1];
}
if (a[n]<0) {
a[n]=b[n]-abs(a[n])%b[n];
} else {
a[n]%=b[n];
}
cout<<a[n]<<endl;
return 0;
}
```

CRT
#include"stdio.h"
#include"iostream"
using namespace std;
typedef long long ll;
int n,m[50],a[50];
void E_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
if(!b) {d=a;x=1;y=0;}
else{E_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
ll CRT()
{
ll M=1;
ll ans=0;
int i;
for(i=1;i<=n;i++) //M=m1*m2*m3*...*mn
M=M*m[i];

for(i=1;i<=n;i++) //Mi=M/mi x是Mi的逆元
{
ll d,x,y;
ll Mi=M/m[i];
E_gcd(Mi,m[i],d,x,y);
ans=(ans+a[i]*Mi*x)%M;
}
if(ans<0) ans+=M;
return ans;
}
int main()
{
while(cin>>n)
{
for(int i=1;i<=n;i++)
cin>>m[i]>>a[i];
cout<<CRT()<<endl;
}
return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int n;
long long a,b;
scanf("%d",&n);
long long cur = 0;
long long yin = 1;
while(n--){
long long c,d; scanf("%lld%lld",&c,&d);
while(cur % c != d % c) cur += yin;
yin *= c;
}
printf("%lld",cur);
return 0;
}

提交第一次wrong了两个点，因为如果有 3个猪圈，1个猪剩。至少1只猪就够了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 12;

int m[MAXN], a[MAXN], n;

void exgcd(ll a, ll b, ll&x, ll& y){
if(b == 0){
x = 1, y = 0;
return;

}
exgcd(b, a%b, x, y);
ll tep = x;
x = y;
y = tep - (a/b)*y;
}
ll CRT(){
ll M = 1, ans = 0;
for(int i=1; i<=n; i++) M*=m[i];
for(int i=1; i<=n; i++){
ll x, y;
ll Mi = M/m[i];
exgcd(Mi, m[i], x, y);
ans = (ans + Mi * x * a[i]) % M;
}
if(ans < 0) ans += M;
return ans;
}

int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d%d", &m[i], &a[i]);
printf("%lld\n", CRT());
return 0;
}
NOIP2015赛前留念
祝RP++
——linhui

#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long
LL A[15],T[15],M[15],_M[15];
long long m=1;
LL k_gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(b==0)
{
d=a;
x=1;
y=0;
}
else
{
k_gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
LL inverse(LL a,LL b)
{
LL X=0,Y=0,D=0;
k_gcd(a,b,D,X,Y);
return ((X%b)+b)%b;
}
int main()
{
LL N;
cin>>N;
for(int i=1;i<=N;++i)
{
cin>>M[i]>>A[i];
m*=M[i];
}
for(int i=1;i<=N;++i)
_M[i]=m/M[i];
for(int i=1;i<=N;++i)
T[i]=inverse(_M[i],M[i]);
long long ans=0;
for(int i=1;i<=N;++i)
{
long long aa=T[i]*A[i]*_M[i];
ans+=aa;
}
cout<<ans%m<<endl;
return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n;
vector<long long int>a;
vector<long long int>b;

vector<long long int>f;
long long int ans;

long long int m=1;

int exgcd(long long int a,long long int b,long long int &x,long long int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long int r=exgcd(b,a%b,x,y);
long long int m=x;
x=y;
y=m-(a/b)*y;
return r;
}

int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;++i)
{
scanf("%d",&j);
a.push_back(j);
scanf("%d",&j);
b.push_back(j);
f.push_back(0);
m*=a[i];
}
for(i=0;i<n;++i)
{
exgcd(m/a[i],a[i],f[i],ans);
f[i]=(f[i]%a[i]+a[i])%a[i];//==f[i]=(f[i]+a[i])%a[i]
}
ans=0;
for(i=0;i<n;++i)
{
ans+=b[i]*f[i]*(m/a[i]);
}
cout<<ans%m;//最小值
return 0;
}

记录信息
评测状态 Accepted
题目 P1164 曹冲养猪
递交时间 2015-10-24 15:25:12
代码语言 Pascal
评测机 VijosEx
消耗时间 14 ms
消耗内存 772 KiB
评测时间 2015-10-24 15:25:13
评测结果
编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
13 lines compiled, 0.1 sec , 29328 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #4: Accepted, time = 2 ms, mem = 772 KiB, score = 10
测试数据 #5: Accepted, time = 2 ms, mem = 772 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #8: Accepted, time = 7 ms, mem = 772 KiB, score = 10
测试数据 #9: Accepted, time = 3 ms, mem = 772 KiB, score = 10
Accepted, time = 14 ms, mem = 772 KiB, score = 100
代码
var
a,b,c,d:qword;
n,i:longint;
begin
readln(n);
readln(a,b);
for i:=2 to n do
begin
readln(c,d);
while b mod c<>d do b:=a+b;
a:=a*c;
end;
writeln(b);
end.

很裸的中国剩余定理
记 同余方程为 ans% a[i]=b[i];
M=a[1]*a[2]*...*a[n];M[i]=M/a[i];t[i]为M[i]关于a[i]的逆元 则答案为( (b[1]*a[1]*t[1]+....b[n]*a[n]*t[n] ) % M+ M)%M

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL a[20],b[20],n,t,M=1,ni[20],t2,ans;

void exgcd(LL a,LL b,LL &d,LL &x,LL &y){//d是gcd a,b,x,y,满足ax+by=d
if(!b) {d=a;x=1;y=0;}
else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}

int main(){
//freopen("1164.in","r",stdin);freopen("1164.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]),M*=a[i];
for(int i=1;i<=n;i++){
exgcd(M/a[i],a[i],t,ni[i],t2);
ni[i]=(ni[i]%a[i]+a[i])%a[i];
(ans+=b[i]*ni[i]*(M/a[i]))%=M;
}
if(ans<0) ans+=M;
printf("%lld",ans);
return 0;
}

中国剩余定理，见黑书P230。

void solve() {
    for (int i = 1; i <= n; i++) {
        long long Mi = M / m[i], x, y;
        exgcd(Mi, m[i], x, y);
        ans = (ans + Mi * x * a[i]) % M;
    }
}

中国剩余定理......

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL gcl(LL x,LL y)
{
if(x % y == 0)
return y;
else
return ass(y,x % y);
}
int main()
{
while(scanf("%d",&n) == 1)
{
LL num = 0;
LL ans = 0;
LL k = 0;
LL a,b;
for(int i = 1; i <= n; i++)
{
scanf("%I64d%I64d",&a,&b);
if(i == 1)
{
num = b;
ans = a;
continue;
}
for(int j = 0;;j++)
{
k = num + ans * j;
if(k % a == b)
break;
}
num = k;
if(ans < b)
swap(ans,b);
ans = (ans * a) / gcl(ans,a);
}
printf("%I64d\n",num);
}
}

#include<iostream>

using namespace std;

int main()
{
int n, a, b;
cin>>n;
cin>>a>>b;
long long int gcd = a, ans = b;
for(int i=2; i<=n; i++){
cin>>a>>b;
while(ans % a != b)
ans += gcd;

gcd *= a;

}

cout<<ans;
return 0;
}
水一发