SYCOJ798Biorhythms

https://oj.shiyancang.cn/Problem/798.html

#include
using namespace std;
typedef long long ll;
const int mod = 21252;
ll a[4],m[4];
ll M;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1,y=0;return a;}
    ll d=ex_gcd(b,a%b,x,y);
    ll temp=x;x=y;y=temp-a/b*y;
    return d;
}
ll crt(ll n)
{
    ll i,Mi,xi,yi,d,Ans=0;
    M=1;
    for(i=1;i<=n;i++)M*=m[i];
    for(i=1;i<=n;i++)
    {
        Mi=M/m[i];d=ex_gcd(Mi,m[i],xi,yi);
        Ans=(Ans+Mi*a[i]*xi)%M;
    }
    return (Ans%M+M)%M;//最小整数解，因为gcd为1所以直接M就可以了 
}
int main()
{
    ll k,t=0;
    m[1]=23,m[2]=28,m[3]=33;
    while(~scanf("%lld%lld%lld%lld",&a[1],&a[2],&a[3],&k),a[1]!=-1||a[2]!=-1||a[3]!=-1||k!=-1)
    {
        ll ans=crt(3);
        while(ans<=k) ans+=M;//要超过k才行 
        printf("Case %lld: the next triple peak occurs in ",++t);
        cout<" days.\n";
    }
    return 0;
 } 

特殊情况的中国剩余定理，直接构造，因为gcd为1，并且在模M下具有唯一解，所以正常的模M就可以了。

但是要大于k，所以要到k之后。