excrt扩展剩余定理#include＜iostream＞#include＜cstring＞#include＜vector＞#include＜cstring＞#include＜cmath＞#

83 阅读 0 评论 55 点赞

我是靠谱客的博主坚定小鸭子，最近开发中收集的这篇文章主要介绍excrt扩展剩余定理#include＜iostream＞#include＜cstring＞#include＜vector＞#include＜cstring＞#include＜cmath＞#，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

n个同余方程顺序做n次exgcd，每次以累计lcm作exgcd主元，以新mod作mod，每次ans累加一个exgcd最小值，记得每次ans取累计lcm保证最小正

【模板】扩展中国剩余定理（EXCRT） - 洛谷

#include<iostream>
#include<cstring>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int nn=1e5+50;
ll n,a[nn],b[nn];
inline ll read()
{
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
ll qmul(ll a,ll b ,ll mod)
{
ll ans=0;
while(b>0)
{
if(b&1) ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ((ans%mod)+mod)%mod;
}
ll gcd(ll a, ll b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll gcd=exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return gcd;
}
int main ()
{
n=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
}
for(int i=1;i<=n;++i)
{
b[i]=read();
b[i]=(b[i]%a[i])+a[i];
b[i]%=a[i];
}
ll m=1,ans=0,aa,bb,cc,x,y,d;
for(int i=1;i<=n;++i)
{
bb=b[i],cc=((ans-a[i])%bb+bb)%bb;
aa=m;
d=exgcd(aa,bb,x,y);
if(cc%d!=0)
return -1;
ans+=aa*qmul(x,cc/d,bb);
m=m/d*bb;
ans=(ans%m+m)%m;
}
cout<<ans;
}