洛谷P4777 【模板】扩展中国剩余定理（EXCRT）
发布时间
阅读量：
阅读量
传送门
首先介绍拓展中国剩余定理。
\begin{cases} x\equiv a_1\pmod{p_1}\\ x\equiv a_2\pmod{p_2}\\ \dots\\ x\equiv a_n\pmod{p_n} \end{cases}
拓展中国剩余定理与传统版本的主要区别在于模数p_i是否两两互质。
我们需要计算前i-1项的最小公倍数M。
当加入新的同余式时，则有x + t*M \equiv a_i \pmod{p_i}。
此时我们可以通过扩展欧几里得算法来求解t值。
进而得到新的x = x + t*M。
问题要求我们找到n组非负整数a_i, b_i满足上述方程组，并且寻找满足条件的最小非负整数解x。
需要注意的是x的取值范围不超过1018，在实际计算过程中可能会超过long long范围，
因此我们需要采用快速乘法算法来解决溢出问题。
AC代码如下
/*---------------
author:onebelieve
----------------*/
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rip(i,a,b) for(int i=a;i<=b;i+)
typedef long long ll;
const int N=1e5+10;
using namespace std;
ll n,a[N],b[N];
template<typename T> T quick(T a,T b,T p){T ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
template<typename T> T fmul(T a,T b,T p){T ans=0;while(b){if(b&1)ans=(ans+a)%p;a=a%p<<1%p;b>>=1;}return ans;}
template<typename T> T gcd(T a,T b){return b==0?a:gcd(b,a%b);}
template<typename T> T exgcd(T a,T b,T &x,T &y){
if(b==0){x=1,y=0; return a;}
T Gcd=exgcd(b,a%b,x,y),temp=x;
x=y; y=temp-a/b*x; return Gcd;
}
inline ll excrt()
{
ll M=b[0],ans=a[0],x,y; //x代表我们要找的t
for(int i=1;i<n;i++)
{
ll a1=M,b1=b[i],c=(a[i]-ans%b1+b1)%b1;
ll gcd=exgcd<ll>(a1,b1,x,y),t=b1/gcd; //此时找到的t只是假设a[i]-x=1时的解
if(c%gcd!=0)return -1;
x=fmul<ll>(x,c/gcd,t); //此时的t才是我们要的
ans+=x*M;
M*=t;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
signed main()
{
cin>>n;
rep(i,0,n)cin>>b[i]>>a[i];
cout<<excrt()<<endl;
return 0;
}全部评论 (0)
还没有任何评论哟~