luogu P3868 猜数字

题目描述:给你k个a[i],b[i] 其中(x-a[i])%b[i]=0  求解最小非负解
分析 :这个题解决了一些中国剩余定理的模糊点 ,首先等式不难推到变形得x=a[i](mod b[i])  这里注意几点
            输入a[i]可能是负的所以要把它变正 及a[i]=(a[i]%b[i]+b[i])%b[i];  (原理是不改变等式性质)
            乘法可能会爆long long  所以选择快速乘
            求逆元不能用费马小定理 因为b[i]不一定是素数,要用扩展欧几里德  求出来的逆元别忘记取正了  应为x的通解为 x+i*M  所以全程modM   保证最小
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[12],m[12];
int k;
ll M=1;
ll multi_fast(ll a,ll b){
    ll ans=0;
    while(b){
        if(b&1)ans=(ans+a)%M;
        a=(a+a)%M;
        b>>=1;
    }
    return ans;
}
void exgcd(ll a,ll b,ll &x,ll &y ){
    if(!b){
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
void china(){
    ll ans=0;
    for(int i=0;i<k;i++)M*=m[i];
    for(int i=0;i<k;i++){
        ll x,y;
        exgcd(M/m[i],m[i],x,y);
        x=(x%m[i]+m[i])%m[i];
        ans=(ans+multi_fast(multi_fast(x,a[i]),M/m[i]))%M;
    }
    cout<<ans<<endl;
}
int main(){
    cin>>k;
    for(int i=0;i<k;i++)cin>>a[i];
    for(int i=0;i<k;i++)cin>>m[i];
    for(int i=0;i<k;i++) a[i]=(a[i]%m[i]+m[i])%m[i];
    china();
}




全部评论

相关推荐

02-23 12:32
已编辑
门头沟学院 嵌入式工程师
King987:学历没有问题,然后既然有实习经历的话,把这个放在上面多写一点,哪怕你自己包装一下,只要能圆回来就行,既然有实习经历的话,肯定主要看实习经历之类的。然后也会主要问这里多准备准备
点赞 评论 收藏
分享
牛客963010790号:一般是hr拿着老板账号在招人不是真是老板招
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务