一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。
Input
第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)
第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)
Output
输出符合条件的最小的K。数据中所有K均小于10^9。
Input示例
3
2 1
3 2
5 3
Output示例
23
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std; ll x,y,n,a[],m[];
ll exgcd(ll a,ll b){
if(b==){
x=;y=;return a;
}
ll g=exgcd(b,a%b);
ll t=x;
x=y;
y=t-(a/b)*y;
return g;
} ll CRT()
{
ll M = ;
ll ans = ;
for(ll i=; i<=n; i++)
M *= m[i];
for(ll i=; i<=n; i++)
{
x=, y=;
ll Mi = M / m[i];
exgcd(Mi, m[i]);
ans = (ans + Mi * x * a[i]) % M;
}
if(ans < ) ans += M;
return ans;
} int main(){
// freopen("01.in","r",stdin); scanf("%d",&n);
for(ll i=;i<=n;i++){
scanf("%d%d",&m[i],&a[i]);
}
cout<<CRT()<<endl;
return ;
}转载代码 不予展示
请在弄懂或者背下 扩展欧几里得算法，同余 的概念或代码后来看这道题
建议先去百度百科逛一圈（我已经放弃了wiki。。）
听大神讲CRT http://blog.****.net/acdreamers/article/details/8050018
看大神证明CRT http://blog.****.net/hard_man/article/details/7732795
提示，好好看~