poj 1006 与中国剩余定理

短命女 2022-03-20 19:12 192阅读 0赞

poj 1006 题的思路不是很难的，可以转化数学式：

现设 num 是下一个相同日子距离开始的天数

p，e，i，d 如题中所设！

那么就可以得到三个式子：( num + d ) % 23 == p； ( num + d ) % 28 == e； ( num + d ) % 33 == i；

p，e，i，d 是我们输入的，那么我们需要求出num即可，为了方便，我们将num+d暂时作为一个整体！令x = num + d；

即：x % 23 == p； x % 28 == e； x % 33 == i；求x

怎么办？这就涉及到所谓的 “ **中国剩余定理** ”( 概念自己google，很easy )

《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？”答为“23”。

--------这个就是传说中的“中国剩余定理”。 其实题目的意思就是，n % 3 = 2, n % 5 = 3, n % 7 = 2; 问n是多少？

那么他是怎么解决的呢？

看下面：

题目中涉及 3， 5，7三个互质的数、

令：5 \* 7 \* a % 3 = 1;  --------------> a = 2; 即5 \* 7 \* 2 = 70；

3 \* 7 \* b % 5 = 1;  --------------> b = 1; 即3 \* 7 \* 1 = 21；

3 \* 5 \* c % 7 = 1;  --------------> c  = 1; 即3 \* 5 \* 1 = 15；

**为什么要使余数为1：是为了要求余数2的话，只要乘以2就可以，要求余数为3的话，只要乘以3就可以！**

( 因为题目想要n % 3 =**2**, n % 5 =**3**, n % 7 =**2**; )

那么：要使得n % 3 = 2，那么（ 5 \* 7 \* 2 ）\***2**  % 3 = 2；( 因为5 \* 7 \* 2 % 3 = 1 )

同理： 要使得n % 5 = 3，那么（ 3 \* 7 \* 1 ）\***3**  % 5 = 3；( 因为3 \* 7 \* 1 % 5 = 1 )

同理：要使得n % 7 = 2，那么（ 3 \* 5 \* 1 ）\* **2**  % 7 = 2；( 因为3 \* 5 \* 1 % 7 = 1 )

**那么现在将（ 5 \* 7 \* 2 ）\* 2和（ 3 \* 7 \* 1 ）\* 3和（ 3 \* 5 \* 1 ）\* 2相加会怎么样呢？我们知道**

**（ 5 \* 7 \* 2 ）\* 2可以被5和7整除，但是%3等于2**

**（ 3 \* 7 \* 1 ）\* 3可以被3和7整除，但是%5等于3**

**（ 3 \* 5 \* 1 ）\* 2可以被3和5整除，但是%7等于2**

**那么即使相加后，%3， 5， 7的情况也还是一样的！**

那么就得到一个我们暂时需要的数（ 5 \* 7 \* 2 ）\* 2 +（ 3 \* 7 \* 1 ）\* 3 +（ 3 \* 5 \* 1 ）\* 2 = 233

但不是最小的!所有我们还要 233 % ( 3 \* 5 \* 7 ) == 23  得解！

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

// 以上就是算法解析，貌似讲的不是很清晰，哎，大家见谅咯~

现在看看此题：x % 23 == p； x % 28 == e； x % 33 == i；求x

按照以上算法：

使 33 \* 28 \* a % 23 = 1，得a = 6； 33 \* 28 \* 6 = 5544；

使23 \* 33 \* b % 28 = 1， 得b = 19；23 \* 33 \* 19 = 14421；   
使23 \* 28 \* c % 33 = 1， 得c = 2；  23 \* 28 \* 2 = 1288。

那么x  =  5544 \* p + 14421 \* e + 1288 \* i

那么x-d即相差的时间天数！

因为有范围限制，那么(x-d) %= 21252；且如果此时<=0，那么(x-d)  += 21252   ，以上都只是为了保证在范围内而已~

AC代码如下：

/*
      中国剩余定理:出自《孙子算经》
      
    */
    
    #include<stdio.h>
    
    #define MAX 21252
    
    int main()
    {
    	int p, e, i, d, n, count = 0;
    	
    	while( scanf("%d%d%d%d", &p, &e, &i, &d) != EOF )
    	{
                    count++;
    		if(p == -1 && e == -1 && i == -1 && d == -1)
    		{
    			break;
                    }
    
    		n = ( 5544 * p + 14421 * e + 1288 * i - d ) % MAX;
    		
    		if( n <= 0 )   // 范围限制 
    		{
    			n += 21252;
                    }
            
    		printf("Case %d: the next triple peak occurs in %d days.\n", count, n );
    	}
    	return 0;
    }