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();
}
韶音科技公司氛围 171人发布
