中国剩余定理.txt

ACM 算法模板,适合搞ACM的人

民间传说着一则故事——“韩信点兵”。 
    秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、 “神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。

在一千多年前的《孙子算经》中，有这样一道算术题： 


今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?

用数学符号描述此题为：求，使其满足：





解此方程有如下歌诀：


三人同行七十稀，五树梅花廿一枝，
七子共党中秋月，除百零五便得知。
意为：用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，再将其相加，然后减105的倍数即可以求得结果。具体计算为：




    观察上式不难发现，70为5和7的倍数且3除恰好余1；21为3和7的倍数且5除恰好余1；15为3和5的倍数且7除恰好余1。而将70乘除以3的余数2，得到的结果除以3就余2了。
于是，我们的到了如下解法：
1. INPUT 
2. 
3. FOR  DO 
4. 
5. 
6. FOR  DO
    WHILE  DO
        
7. 
8. 
9. FOR  DO 
10. OUTPUT 
11. END 

POJ的1006题，中国剩余定理，终于AC了，主要错误出在以下三个方面
[1]对题目的理解上的偏差
[2]中国剩余定理的算法
[3]对结果<0时的处理
下面是我的AC代码，其中求y[i]的时候算法复杂了，还没看懂最简单的算法。
整个程序使用时间75MS，内存92K。还有很大优化的余地。


 程序代码

#include<iostream>
using namespace std;
main()
{
    int b[3],n[3],y[3],d,i,M,days,times=1;
    int m[3]={23,28,33};
    M=m[0]*m[1]*m[2];
    cin >>b[0]>>b[1]>>b[2]>>d;
    while(b[0]!=-1)
    {
        days=0;
        for(i=0;i<3;i++)
            b[i]=b[i]%m[i];
        for(i=0;i<3;i++)
        {
            int j=1;
            n[i]=M/m[i];
            while((n[i]*j)%m[i]!=1)//用循环计算y[i]应该是整个程序中最烂的算法
                j++;
            y[i]=j;
        }
        for(i=0;i<3;i++)
            days=days+b[i]*y[i]*n[i];
        days=(days+M)%M;
        days=days-d;
        if(days<=0)days+=M;
        cout <<"Case "<<times<<": the next triple peak occurs in "<<days<<" days."<<endl;
        times++;
        cin >>b[0]>>b[1]>>b[2]>>d;
    }
}