写在前面
本篇主要介绍拓展中国剩余定理（EXCRT），如果没有学习中国剩余定理的推荐先学一下。
其实也无所谓，反正这俩也没啥关系吧。。
戳这里学习中国剩余定理。
导入
众所周知，中国剩余定理可以求解同余方程组
[left{
egin{aligned}
& x equiv c_1 pmod{m_1} \
& x equiv c_2 pmod{m_2} \
& cdots \
& x equiv c_n pmod{m_n}
end{aligned}
ight.
]
其中 (m_1,m_2,cdots,m_n) 两两互质。
思路
求解同余方程
[ left{ egin{aligned} & x equiv c_1 pmod{m_1} \ & x equiv c_2 pmod{m_2} \ & cdots \ & x equiv c_n pmod{m_n} end{aligned} ight. ]其中 (m_1,m_2,cdots,m_n) 不满足两两互质。
注意到此同余方程中的模数不互质，自然不可以用中国剩余定理解决。
首先，对于两个式子
[egin{aligned}
x equiv c_1 pmod{m_1} \
x equiv c_2 pmod{m_2}
end{aligned}
]
变形有
[egin{aligned}
x=c_1+m_1k_1 \
x=c_2+ m_2k_2
end{aligned}
]
联立
[c_1 + m_1k_1 = c_2+m_2k_2
]
移项
[m_1k_1 = c_2-c_1+m_2k_2
]
由于 (cfrac{(c_2-c_1)}{gcd(m_1,m_2)}) 必须为整数，所以该方程有解的充要条件为 (gcd(m_1,m_2) mid (c_2-c_1))。
对于上述方程，两边同时除以 (gcd(m_1,m_2))
[egin{aligned}
cfrac{m_1k_1}{gcd(m_1,m_2)} &= cfrac{c_2-c_1}{gcd(m_1,m_2)} + cfrac{m_2k_2}{gcd(m_1,m_2)} \
cfrac{m_1}{gcd(m_1,m_2)}k_1 &= cfrac{c_2-c_1}{gcd(m_1,m_2)}+cfrac{m_2}{gcd(m_1,m_2)}k_2
end{aligned}
]
转化为
[cfrac{m_1}{gcd(m_1,m_2)}k_1 equiv cfrac{c_2-c_1}{gcd(m_1,m_2)} pmod{cfrac{m_2}{gcd(m_1,m_2)}}
]
此时 (k_2) 成功消去
同余式两边同时除以 (cfrac{m_1}{gcd(m_1,m_2)}) 有
[k_1 equiv inv(cfrac{m_1}{gcd(m_1,m_2)},cfrac{m_2}{gcd(m_1,m_2)}) cdot cfrac{c_2-c_1}{gcd(m_1,m_2)} pmod{cfrac{m_2}{gcd(m_1,m_2)}}
]
其中 (inv(a,b)) 表示 (a) 在 (pmod b) 意义下的逆元，则有
[k_{1} = inv left( cfrac{m_{1}}{left(m_{1}, m_{2}
ight)}, cfrac{m_{2}}{left(m_{1}, m_{2}
ight)}
ight) cdot cfrac{left(c_{2}-c_{1}
ight)}{left(m_{1}, m_{2}
ight)}+cfrac{m_{2}}{left(m_{1}, m_{2}
ight)} cdot y
]
将 (k_1) 带入到最开始的两个式子
[x = invleft(cfrac{m_1}{gcd(m_1,m_2)},cfrac{m_2}{gcd(m_1,m_2)}
ight) cdot cfrac{c_2-c_1}{gcd(m_1,m_2)} cdot m_1 + y cdot cfrac{m_1m_2}{gcd(m_1,m_2)} + c_1
]
转化为
[x equiv invleft(cfrac{m_1}{gcd(m_1,m_2)},cfrac{m_2}{gcd(m_1,m_2)}
ight) cdot cfrac{c_2-c_1}{gcd(m_1,m_2)} cdot m_1 +c_1 pmod{cfrac{m_1m_2}{gcd(m_1,m_2)}}
]
此时，该式便可以看作
[x equiv c pmod m
]
推广
若出现多个同余式合并，可以将其中两个先合并，得到一个新的同余式，然后再将其与其他同余式合并。
重复上述操作，直到完全合并。
例题
P4777 【模板】扩展中国剩余定理（EXCRT）
/*
Name: P4777 【模板】扩展中国剩余定理（EXCRT）
Solution: 扩展中国剩余定理
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
/*==================================================快读*/
inline int read()
{
int X = 0, F = 1;
char CH = getchar();
while (CH < '0' || CH > '9')
{
if (CH == '-')
F = -1;
CH = getchar();
}
while (CH >= '0' && CH <= '9')
{
X = (X << 3) + (X << 1) + (CH ^ 48);
CH = getchar();
}
return X * F;
}
/*===============================================定义变量*/
int n;
const int _ = 100010;
int a[_], b[_];
/*=============================================自定义函数*/
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int res = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - a / b * y;
return res;
}
int Qmul(int a, int b, int p)
{
int res = 0;
while (b)
{
if (b & 1)
res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
int excrt()
{
int x, y;
int m = b[1];
int res = a[1];
for (int i = 2; i <= n; i++)
{
int a_ = m, b_ = b[i];
int c_ = (a[i] - res % b_ + b_) % b_;
int gcd = exgcd(a_, b_, x, y);
int bb = b_ / gcd;
if (c_ % gcd)
return -1;
x = Qmul(x, c_ / gcd, bb);
res += x * m;
m *= bb;
res = (res % m + m) % m;
}
return res;
}
/*=================================================主函数*/
signed main()
{
n = read();
for (int i = 1; i <= n; i++)
{
b[i] = read();
a[i] = read();
}
printf("%lld
", excrt());
return 0;
}
P3868 [TJOI2009]猜数字
板子题，但是注意要用快速乘。
/*
Name: P3868 [TJOI2009]猜数字
Solution: 中国剩余定理
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
/*==================================================快读*/
inline int read()
{
int X = 0, F = 1;
char CH = getchar();
while (CH < '0' || CH > '9')
{
if (CH == '-')
F = -1;
CH = getchar();
}
while (CH >= '0' && CH <= '9')
{
X = (X << 3) + (X << 1) + (CH ^ 48);
CH = getchar();
}
return X * F;
}
/*===============================================定义变量*/
int n;
int a[100010], b[100010];
int ans;
/*=============================================自定义函数*/
int Qmul(int A, int B, int mod)
{
int ans = 0;
while (B > 0)
{
if (B & 1)
ans = (ans + A % mod) % mod;
A = (A + A) % mod;
B >>= 1;
}
return ans;
}
int exgcd(int A, int B, int &x, int &y)
{
if (!B)
{
x = 1, y = 0;
return A;
}
int d = exgcd(B, A % B, x, y);
int tmp = x;
x = y, y = tmp - A / B * y;
return d;
}
int lcm(int A, int B)
{
int xxx, yyy;
int g = exgcd(A, B, xxx, yyy);
return (A / g * B);
}
int excrt()
{
int x, y;
int M = b[1], ans = a[1];
for (int i = 2; i <= n; i++)
{
int A = M, B = b[i];
int C = (a[i] - ans % B + B) % B;
int g = exgcd(A, B, x, y);
if (C % g)
return -1;
x = Qmul(x, C / g, B);
ans += x * M;
M = lcm(M, B);
ans = (ans % M + M) % M;
}
return ans;
}
/*=================================================主函数*/
signed main()
{
n=read();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
{
b[i] = read();
a[i] = (a[i] + b[i]) % b[i];
}
printf("%lld
", excrt());
return 0;
}
大数翻倍法
这里介绍一种暴力合并求解同余方程的奇妙方法。
思路
还是本文导入中的同余方程，先关注其中两个
[left{
egin{aligned}
x equiv c_1 pmod{m_1} \
x equiv c_2 pmod{m_2}
end{aligned}
ight.
]
设初始的 (x=0,m=1)，合并第一个方程后变为 (x=a_1,m=m_1)，那么现在只需满足第二个同余方程即可。
而此时已知
[a_1+km_1 pmod{m_1} =a_1
]
所以可以直接暴力加和 (m_1) ，直到可以满足第二个同余方程。
若出现一个能满足条件的情况就合并，而模数要合并为 (operatorname{lcm}(m_1,m_2)) 。
Tips:
这里有一个小优化，不难证明，更小的模数会使复杂度更优，所以可以对此进行判断，然后转换，再枚举即可。
最后代码：
void merge(int &a1, int &m1, int a2, int m2)
{
if (m1 < m2)
{
swap(m1, m2);
swap(a1, a2);
}
while (a1 % m2 != a2)
a1 += m1;
m1 = lcm(m1, m2);
}
时间复杂度 (Oleft(sumlimits_{i=1}^nm_i ight)) 可以接受。
具体时间复杂度度的证明可以看这里。
例题
P4777 【模板】扩展中国剩余定理（EXCRT）
/*
Name: P4777 【模板】扩展中国剩余定理（EXCRT）
Solution: v2.0
大数翻倍法
By Frather_
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define int long long
#define InF 0x3f3f3f3f
#define kMax 10e5
#define kMin -10e5
#define kMod 998244353
using namespace std;
/*==================================================快读*/
inline int read()
{
int X = 0, F = 1;
char CH = getchar();
while (CH < '0' || CH > '9')
{
if (CH == '-')
F = -1;
CH = getchar();
}
while (CH >= '0' && CH <= '9')
{
X = (X << 3) + (X << 1) + (CH ^ 48);
CH = getchar();
}
return X * F;
}
/*===============================================定义变量*/
int n;
int a = 0, m = 1, a_, m_;
/*=============================================自定义函数*/
inline int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
inline int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
void merge(int &a1, int &m1, int a2, int m2)
{
if (m2 > m1)
{
swap(a1, a2);
swap(m1, m2);
}
while (a1 % m2 != a2)
a1 += m1;
m1 = lcm(m1, m2);
}
/*=================================================主函数*/
signed main()
{
n = read();
for (int i = 1; i <= n; i++)
{
m_ = read();
a_ = read();
a_ %= m_;
merge(a, m, a_, m_);
}
printf("%lld
", a);
return 0;
}