中国剩余定理 P1495 【模板】中国剩余定理(CRT)/曹冲养猪

 1 #include
 2 using namespace std;
 3 typedef long long ll; 
 4 const int N=1e5+5;
 5 ll a[N],mod[N],ans,n,mulsum=1;
 6 ll read()
 7 {
 8     ll x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
11     return x*f;
12 }
13 ll exgcd(ll a, ll b, ll &x, ll &y)
14 {
15     if(!b)
16     {
17         x=1,y=0;
18         return a;
19     }
20     ll d=exgcd(b,a%b,x,y);
21     ll t=x;
22     x=y;y=t-a/b*y;
23     return d;
24 }
25 int main()
26 {
27     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
28     n=read();
29     for(int i=1;i<=n;i++)mod[i]=read(),a[i]=read(),mulsum*=mod[i];
30     for(int i=1;i<=n;i++)
31     {
32         ll x,y;
33         ll mi=mulsum/mod[i];
34         exgcd(mi,mod[i],x,y);
35         x=((x%mod[i])+mod[i])%mod[i];
36         ans=(ans+(x*mi*a[i]))%mulsum;    
37     }
38     cout<"\n";
39     return 0;
40 }