啊这题和东方没关系……我是在黑初中时候某个同学（

p.s.CaO是氧化钙（

 

题目描述

自从CaO冲搞定♂了大象以后，CaOCaO就开始捉摸让儿子干些事业，于是派他到中原养zdx场养zdx，

可是CaO冲满不高兴，于是在工作中马马虎虎，有一次CaOCaO想知道母猪的数量，于是CaO冲想狠

狠耍CaOCaO一把。举个例子，假如有16头母zdx，如果建了3个zdx圈，剩下1头zdx就没有地方安家

了。如果建造了5个zdx圈，但是仍然有1头zdx没有地方去，然后如果建造了7个zdx圈，还有2头没有

地方去。你作为CaO总的私人秘书理所当然要将准确的zdx数报给CaO总，你该怎么办？

输入

第一行包含一个整数n (n <= 10) – 建立zdx圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000),

 表示建立了ai个zdx圈，有bi头zdx没有去处。你可以假定ai,aj互质.

输出

输出包含一个正整数，即为CaO冲至少养母zdx的数目。

zdx不是猪谁是猪呢（

这题似乎又和exgcd有关系……

中国剩余定理：

当a[i]都为素数

M=a[1]*a[2]*...*a[n]

X=k1+k2+...+kn

ki %a[i]= b[i]

ki %a[j]=0 i!=j

inv(x,y) 为x在mod y意义下的逆元

ki=(M/a[i])*inv((M/a[i]),a[i])*b[i]

X%3=2

X%5=3

X%7=2

M=3*5*7=105

X=k1+k2+k3

k1=35*inv(35,3)*2

=35*2*2=140 = 35

k2=21*1*3=63

k3=15*1*2=30

X=128%M = 23

O(nlogn)

int inv(int a,int b){// 求 mod b意义下 a的逆元

int x,y;

exgcd(a,b,x,y);

return x%b;

}

ak % b = 1

扩展欧几里得 两两合并

n

X%a[i] = b[i]

X % a1 = b1 -> X+ k1*a1 = b1

X % a2 = b2 -> X+ k2*a2 = b2

k1*a1 - k2*a2 = b1-b2

ax+by = c

exgcd(a1,-a2,k1,k2);

X % a1a2 = ?

　　　　　　　　　　　　　——zrt

仍然不懂

zrt大佬写的剩余定理代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 //by zrt 5 //problem: 6 using namespace std; 7 const int inf=(1<<30); 8 typedef long long LL; 9 const double eps=1e-8;10 int M=21252;11 void exgcd(LL a,LL b,LL&d,LL&x,LL&y){12     if(!b) d=a,x=1,y=0;13     else{14         exgcd(b,a%b,d,y,x);y-=(a/b)*x;15     } 16 }17 LL R1,R2,R3;18 int p,e,i,D;19 int main(){20     //-x/2 = -(x/2)21     printf("%d %d\n",(-3)/2,-3>>1);22     LL y,d;23     exgcd(M/23,23,d,R1,y);24     exgcd(M/28,28,d,R2,y);25     exgcd(M/33,33,d,R3,y);26     R1=(M/23*R1)%M;27     R2=(M/28*R2)%M;28     R3=(M/33*R3)%M;29     int tt=0;30     31     while(scanf("%d%d%d%d",&p,&e,&i,&D),~p){32         printf("Case %d: the next triple peak occurs in ",++tt);33         LL ans=(R1*p+R2*e+R3*i-D)%M;34         ans=(ans+M)%M;35         if(ans==0){36             printf("%d days.\n",M);37         }else printf("%lld days.\n",ans);38     }39     return 0;40 }
       
      
     

标程题解：

1 #include
     
       2 #include
      
        3 using namespace std; 4 #define N 5050 5 typedef long long LL; 6 LL m[N]; 7 LL M=1,n,ans; 8 LL t[N],Mn[N],MM[N]; 9  10 LL exgcd(LL a,LL b,LL &x,LL &y)11 {12     if(b==0)13     {14         x=1,y=0;return a;15     }16     else17     {18         LL t=exgcd(b,a%b,y,x);19         y-=x*(a/b);20         return t;21     }22 }23  24 LL CRT()25 {26     LL temp;27     for(LL i=1;i<=n;i++)28     {29         MM[i]=M/m[i];30         LL k=exgcd(MM[i],m[i],Mn[i],temp);31         ans+=(MM[i]*Mn[i]*t[i]);32     }33     return ((ans%M)+M)%M;34 }35  36 int main()37 {38     freopen("cao.in","r",stdin);39     freopen("cao.out","w",stdout);40     cin>>n;41     for(LL i=1;i<=n;i++)42     {43         scanf("%d%d",&m[i],&t[i]);44         M*=m[i];45     }46      47     cout<
       
        <
       
      
     

都tm不是我的代码

没了