【CRT】Biorhythms

怼烎@ 2024-03-22 16:14 63阅读 0赞

[E-Biorhythms\_牛客竞赛数学专题班同余与模（逆元、费马小定理、欧拉定理、孙子定理） (nowcoder.com)][E-Biorhythms_ _nowcoder.com]

题意：

![9fed94c6b87f4882a8a12a6195a3fce1.png][]

思路：

其实就是求这样的方程组：

![ba5ca2076ad844b8b33d4e9bc262d4c1.jpeg][]

CRT模板

在求CRT时，逆元用欧拉定理求

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=3e6+10;
    const int mxe=3e5+10;
    const int mod=1e9+9;
    
    int d,LCM=1;
    int m[4]={0,23,28,33};
    int M[mxn],a[4];
    
    void CRT_init(){
        for(int i=1;i<=3;i++) LCM*=m[i];
        for(int i=1;i<=3;i++) M[i]=LCM/m[i];
    }
    int ksm(int a,int b,int Mod){
        int res=1ll;
        while(b){
            if(b&1) res=(res*a)%Mod;
            a=(a*a)%Mod;
            b>>=1;
        }
        return res;
    }
    int phi(int x){
        int res=x;
        for(int i=2;i<=x/i;i++){
            if(x%i==0){
                while(x%i==0){
                    x/=i;
                    res=res/i*(i-1);   
                }
            }
        }
        if(x>1) res=res/x*(x-1);
        return res;
    }
    int inv(int x,int Mod){
        return ksm(x,phi(Mod)-1,Mod);
    }
    int CRT(){
        int ans=0;
        for(int i=1;i<=3;i++){
            ans=(ans+M[i]*inv(M[i],m[i])%LCM*a[i]%LCM)%LCM;
        }
        return ans;
    }
    void solve(){
        for(int i=1;i<=3;i++) cin>>a[i];
        cin>>d;
        int ans=CRT()-d;
        if(ans<=0) ans+=LCM;
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        CRT_init();
        while(__--)solve();return 0;
    }

[E-Biorhythms_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/21289/E
[9fed94c6b87f4882a8a12a6195a3fce1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a089cc3e0eaf4ddfb77a6787ae13649f.png
[ba5ca2076ad844b8b33d4e9bc262d4c1.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d76961255b474b4887a012fb71d15dae.png

【CRT】Biorhythms

发表评论取消回复

还没有评论，来说两句吧...

相关阅读