中国剩余定理
中国剩余定理常用来求解同余方程组，形如
\[x \equiv a_i \pmod m_i\] 的方程组首先，我们来讨论模数互质的：
对于这类问题应该怎么求解呢？
（果然我只是会背个板子）
首先，我们定义\[M=\prod m_i\] 然后令\[M_i = \frac{M}{m_i}\] 定义\[t_i为M_i 在 mod\ m_i意义下的逆元\] （这里求逆元可以使用exgcd来求）则最终的解就是
\[ans=\sum_i{M_it_ia_i}\]
#include#include #include #include #include #define ll long longusing namespace std;inline ll read(){ ll x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}const int maxn = 210;ll m[maxn],a[maxn];ll n;ll ans;ll M=1;void exgcd(ll &x,ll &y,ll a,ll b){ if (b==0) { x=1;y=0; return; } exgcd(x,y,b,a%b); int tmp = x; x=y; y=tmp-a/b*y;}void crt(){ for (int i=1;i<=n;i++) { ll Mi=M/m[i]; ll ti=0,y=0; exgcd(ti,y,Mi,m[i]); ans=(ans+Mi*ti%M*a[i]%M)%M; } while (ans<0) { ans+=M; }}int main(){ n=read(); for (int i=1;i<=n;i++) m[i]=read(),a[i]=read(),M=M*m[i]; crt(); cout< <
扩展中国剩余定理
那么如果模数不是互质的呢
这时候就需要拓展CRT了
对于
\[x \equiv a_1 \pmod {m_1}\]\[x \equiv a_2 \pmod {m_2}\]它等价于
\[x=a_1+k_1m_1\]\[x=a_2+k_2m_2\]联立之后，就能得到一个不定方程
\[k_1m_1-k_2m_2=a_2-a_1\]
根据裴蜀定理，我们知道如果\(gcd(m_1,m_2) | (a_2-a_1)\)，那么这个方程就有整数解
则\(k_1=\frac{m_2}{g}t+k_1'\)
设最小正整数解为\(k_1'\)
那么\(x=a_1+k_1m_1=a_1+\frac{m_2}{g}tm_1+k_1'm_1\)
我们设\(a_1+k_1'm_1\)为x_0
那么\(x=x_0+\frac{m_1m_2}{gcd(m1,m2)}t\)
则新的方程就变成了\[x \equiv x_0 \pmod {lcm(m1,m2)}\]
引入一道例题
poj2891#include#include #include #include #include using namespace std;inline long long read(){ long long x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}const int maxn = 1e6+1e2;long long m[maxn],a[maxn];long long M;long long ans;long long x0;long long gcd;int n;long long exgcd(long long &x,long long &y,long long a,long long b){ if (b==0) { x=1; y=0; return a; } long long cnt=exgcd(x,y,b,a%b); long long tmp = x; x=y; y=tmp-a/b*x; return cnt;} long long solve(){ x0=a[1];//x0表示从第一个式子开始，合并到当前点的前一个时a是多少 M=m[1];//M同x0 long long x=0,y=0; for (int i=2;i<=n;i++) { gcd=exgcd(x,y,M,m[i]); if ((a[i]-x0)%gcd!=0) return -1;//判断不定方程的右边能不能整除gcd x=x*(a[i]-x0)/gcd;//扩大相应的倍数 long long tmp = m[i]/gcd; x=(x%tmp+tmp)%tmp;//根据特解公式，防止爆掉 x0=x*M+x0;//求合并完的x0 M=M*m[i]/gcd; x0=x0%M; } x0=(x0+M)%M; return x0;}int main(){ while (scanf("%d",&n)!=EOF) { for (int i=1;i<=n;i++) m[i]=read(),a[i]=read(); printf("%lld\n",solve()); } return 0;}