UVA756：https://www.luogu.org/problemnew/show/UVA756
思路
几乎是裸的中国剩余定理模板题
但是需要注意的是此题并不是求最小正整数解
而是求大于d的解
因此对于ans我们需要分类讨论
当ans<=d时 ans=M-(d-ans)当ans>d时 输出ans即可
代码
#include<iostream>
#include<cstdio>
using namespace std;
int d,M=
23*
28*
33,ans,t;
int m[
4]={
0,
23,
28,
33};
//存mod数
int a[
4];
void exgcd(
int a,
int b,
int &d,
int &x,
int &
y)
{
if(!
b)
{
x=
1;
y=
0;
d=
a;
}
else
{
exgcd(b,a%
b,d,x,y);
int t=
x;
x=
y;
y=t-a/b*
y;
}
}
int intchina(
int n)
//中国剩余定理
{
ans=
0;
//注意初始化
int Mi,x,y,g;
for(
int i=
1;i<=n;i++
)
{
Mi=M/
m[i];
exgcd(Mi,m[i],g,x,y);
ans=(ans+Mi*x*a[i])%
M;
}
if(ans<=d)
return 21252-(d-
ans);
else return ans-d;
//ans的分类讨论
}
int main()
{
while(
1)
{
t++
;
scanf("%d%d%d%d",&a[
1],&a[
2],&a[
3],&
d);
if(a[
1]==-
1&&a[
2]==-
1&&a[
3]==-
1&&d==-
1)
break;
a[1]%=
23,a[
2]%=
28,a[
3]%=
33;
ans=intchina(
3);
printf("Case %d: the next triple peak occurs in %d days.\n", t, ans);
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9671808.html
