hdu 1370：Biorhythms（中国剩余定理）

素颜马尾好姑娘i 2023-07-04 08:40 15阅读 0赞

# hdu 1370：Biorhythms（中国剩余定理） #

[题目链接][Link 1]

**题意：**

看题意一脸懵逼，原来就是求a  
其中  
**(a+d)%23=p  
(a+d)%28=e  
(a+d)%33=i**  
（d，p，e，i 如题意）

**题解：**

很明显的中国剩余定理，虽然证明有点没搞明白，但是有模板啊。。。。

至于中国剩余定理的原理，以前看的一篇博客感觉写的挺好的  
[https://blog.csdn.net/bo\_jwolf/article/details/9355937][https_blog.csdn.net_bo_jwolf_article_details_9355937]

于是一顿操作猛如虎，写了下面代码：

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000000007
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=100000;
    const double eps=1e-8;
    int b[5],w[5],d;
    int extgcd(int a,int b,int &x,int &y){
        
        if(b==0){
        
            x=1;
            y=0;
            return a;
        }
        int d=extgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return d;
    }
    int china(int k){
        
        ll n=1;
        int x,y;
        int a=0;
        for(int i=0;i<k;i++){
        
            n*=w[i];
        }
        for(int i=0;i<k;i++){
        
            int m=n/w[i];
            int d=extgcd(w[i],m,x,y);
            a=(a+y*m*b[i])%n;
        }
        if(a>0){
        
            return a;
        }
        else{
        
            return a+n;
        }
    }
    int main(){
        
        w[0]=23,w[1]=28,w[2]=33;
        int t;
        scanf("%d",&t);
        while(t--){
        
            int cnt=1;
            while(~scanf("%d%d%d%d",&b[0],&b[1],&b[2],&d)){
        
                if(b[0]==-1&&b[1]==-1&&b[2]==-1&&d==-1){
        
                    break;
                }
                printf("Case %d: the next triple peak occurs in ",cnt);
                printf("%d",china(3)-d);
                printf(" days.\n");
                cnt++;
            }
        }
        return 0;
    }

结果wa…

觉得可能是暴int了，进行了下优化就AC了

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000000007
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=100000;
    const double eps=1e-8;
    ll b[5],w[5],d;
    //拓展欧几里得
    ll extgcd(ll a,ll b,ll &x,ll &y){
        
        if(b==0){
        
            x=1;
            y=0;
            return a;
        }
        ll d=extgcd(b,a%b,x,y);
        ll t=x;
        x=y;
        y=t-a/b*y;
        return d;
    }
    //中国剩余定理
    ll china(int k){
        
        ll n=1;
        ll x,y;
        ll a=0;
        for(int i=0;i<k;i++){
        
            n*=w[i];
        }
        for(int i=0;i<k;i++){
        
            ll m=n/w[i];
            ll d=extgcd(w[i],m,x,y);
            a=(a+y*m*b[i])%n;
        }
        if(a>0){
        
            return a;
        }
        else{
        
            return a+n;
        }
    }
    int main(){
        
        w[0]=23,w[1]=28,w[2]=33;
        int t;
        scanf("%d",&t);
        int cnt=1;
        while(~scanf("%lld%lld%lld%lld",&b[0],&b[1],&b[2],&d)){
        
            if(b[0]==-1&&b[1]==-1&&b[2]==-1&&d==-1){
        
                break;
            }
            b[0]%=23,b[1]%=28,b[2]%=33;
            printf("Case %d: the next triple peak occurs in ",cnt);
            ll ans=china(3)-d;
            if(ans<=0){
        
                ans+=23*28*33;
            }
            printf("%lld",ans);
            printf(" days.\n");
            cnt++;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1370
[https_blog.csdn.net_bo_jwolf_article_details_9355937]: https://blog.csdn.net/bo_jwolf/article/details/9355937