Onway

pku1006
中國剩余定理

題意：每個人都有三個天賦，分別是體能，智商，情商。這三個天賦都有一個最高點。每個天賦的最高點都有出現的周期，分別是23,28,33天。假設三個天賦在某一年的第p,i,e三天分別出現了。問，從該年的第n天開始，還要經過多少天，這三個天賦會在同一天出現。

中國剩余定理（中國古代求解一次同余式組的方法）

引出：
公元前后的《孫子算經》中有“物不知數”問題：“今有物不知其數，三三數之余二 ，五五數之余三 ，七七數之余二，問物幾何？”答為“23”

方法：
設總數n,三個除數分別為a,b,c，三個余數依次為p,i,e，即：
n%a==p;
n%b==i;
n%c==e;

令x滿足x%b==0&&x%c==0&&x%a==1,y滿足y%a==0,y%c==0,y%b==1,z滿足z%a==0,z%b==0,z%c==1;

則n=x*p+y*i+z*e分別除以a,b,c，余數必分別為p,i,e.

當然n不一定是滿足條件的最小數。通過將n對a*b*c求余即可得到滿足條件的最小數。

當時對這個方法了解不清，半懂不懂得調試了很久。明白了這個定理以后，其實就水題一道。

這個題目要注意的地方是三個天賦一起出現的那一天可能出現在給出的日期前面。這樣的話，只要將出現的那一天加上一個“大周期”即為第二次出現的天數。