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求余即可得到满足条件的最小数。

当时对这个方法了解不清，半懂不懂得调试了很久。明白了这个定理以后，其实就水题一道。

这个题目要注意的地方是三个天赋一起出现的那一天可能出现在给出的日期前面。这样的话，只要将出现的那一天加上一个“大周期”即为第二次出现的天数。