51nod1079中国剩余定理

发表于 | 分类于 | 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 *中国剩余定理
 */
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#define  LL __int64
using namespace std;
/**
 *gcd(a,b)=d;则存在x,y,使d=ax+by
 *extended_euclid(a,b)=ax+by
 */
LL extended_euclid(LL a,LL b,LL &x,LL &y){//扩张欧几里的算法
    int d;
    if(b==0){
        x=1; y=0;
        return a;
    }
    d=extended_euclid(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
/**
 *x=b[i](modw[i]) o<i<len
 *w[i]>0,且w[]中任意两个数互质
 */
LL chinese_remainder(int b[],int w[],int len){
    LL res,i,d,x,y,n,m;
    res=0; n=1;
    for(i=0;i<len;i++) n*=w[i];
    for(i=0;i<len;i++){
        m=n/w[i];
        extended_euclid(w[i],m,x,y);
        res=(res+y*m*b[i])%n;
    }
    return (n+res%n)%n;
}

int main()
{
	int len,b[12],w[12];
	while(cin>>len){
        for(int i=0;i<len;i++){
            cin>>w[i]>>b[i];
        }
        cout<<chinese_remainder(b,w,len)<<endl;

	}
	return 0;
}