Question

请教，poj 1006 Biorhythms为什么通过不了？ answer wrong.

#include<stdio.h>
int main(){
int a,b,c,n,i=1;
while(scanf("%d %d %d %d",&a,&b,&c,&n)&&(a+b+c+n)!=-4){
int x,flag=1;
for(x=1;flag;x++){
if((((23*x+a-b)%28)==0)&&(((23*x+a-c)%33)==0)){
printf("Case %d: the next triple peak occurs in %d days.\n",i,23*x-n);
flag=0;
}
}
i++;
}
return 0;
}

Answer 1

【解题思路】
中国剩余定理【孙子定理】详解：
其实就是解方程组：
求res的值
使用中国剩余定理的条件【重要！！！】：
n1，n2，n3……ni 这些数两两互质(互素)！！也就是两两之间的最大公约数是1！！
回到正题：先看一下这个视频，后面的会更好理解！
http://v.youku.com/v_show/id_XMTExNTAzOTIw.html
算法描述：【利用同余的加性和乘性】
令nn = n1×n2×n3×……×ni;
那么也就是说nn是ni的倍数！
所以有：nn/ni是其他n的倍数，不是ni的倍数，而且nn/ni跟ni没有大于1的公约数
【如nn/n2，是n1,n3,n4...的倍数，但不是n2的倍数，而且nn/n2和n2的最大公约数是1，因为上面说了这些数两两互质】
既然nn/ni是其他n的倍数，那么nn/ni这个数模其他n【n1,n2...n[i-1],n[i+1]...】的结果肯定是0，为下面利用同余的加性奠定了基础
所以根据视频那种方法
可以先找到x使得：

假设找到这个x了，那么要满足第i个方程，则利用同余的乘性必有：

那么就是res的一部分，它使得res满足第i个方程
所以利用同余的加性，把满足所有方程的这么一个部分加起来就是求出来的其中一组解了
怎么找x呢？【关键】
∵有重要条件：两两互质
∴nn/ni和ni也互质
∴【根据上述:使用中国剩余定理的条件】
∴由扩展的【欧几里得】得：

∴两边同时模ni得：

跟上面的式子对比，发现x = x0
x0怎么求？
不就是利用【扩展欧几里得定理】咯！
另外推荐题目：http://acm.hdu.edu.cn/showproblem.php?pid=1930

【AC源代码】望采纳哦~ 有机会欢迎再问哦~ o(∩_∩)o

#include <stdio.h>
void Egcd (int a, int b, int &x, int &y) //扩展欧几里得【无返回版】求x
{
if (b == 0)
{
x = 1, y = 0;
return ;
}
Egcd (b, a%b, x, y);
int tp = x;
x = y;
y = tp - a/b*y;
}
int CRT (int n[], int b[], int nn)
{
int res = 0, x, y, i;
for (i = 0; i < 3; i++)
{
int a = nn / n[i];
Egcd (a, n[i], x, y); //求x
res += a * x * b[i]; //把所有组成部分加起来【加性】
} //其中*b[i]是利用了同余的乘性
return res;
}
int main()
{
int n[5] = {23, 28, 33}, b[5], i, date, k = 1, x0;
while (1)
{
for (i = 0; i < 3; i++)
scanf ("%d", b+i);
scanf ("%d", &date);
if (date == -1)
break;
x0 = (CRT (n, b, 21252) - date) % 21252; //使解不大于21252
if (x0 <= 0)
x0 += 21252; //负数或0特殊考虑
printf ("Case %d: the next triple peak occurs in %d days.\n", k++, x0);
}
return 0;
}