P4777 【模板】扩展中国剩余定理（EXCRT） 题解
未来姚班zyl
·
·
题解
题目大意
求解同余方程组：
\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases}
## 题目分析
膜拜大佬 [Katyusha_01](https://www.luogu.com.cn/user/533742) 提供的宝贵思路，经同意转述。
我们尊敬的阮老师在题解中提到：
题解区现有的 $24$ 篇题解没有一篇对这段话提出质疑。
给它动小手术是没有用的，吗？
既然都叫 EXCRT 了，我们就要由 CRT 扩展出新的做法！
大佬的第一步是，既然模数不互质，那么我们就想办法拆方程，将模数转化为互质的，就可以使用 CRT 了。
我们能想到的唯一方法就是质因数分解了。我们有以下结论：
> 同余方程 $x \equiv b\ ({\rm mod}\ a)$ 等价于方程组 $\begin{cases} x \equiv b\ ({\rm mod}\ p_1^{k_1}) \\ x\equiv b\ ({\rm mod}\ p_2^{k_2}) \\ ... \\ x \equiv b\ ({\rm mod}\ p_m^{k_m})\end{cases}$。其中 $p_i^{k_i}$ 是对 $a$ 质因数分解的结果。
这个结论在 exLucas 中有典型的应用，证明非常简单，无需赘述。
在此题中，有 $a_i$ 的 $\operatorname{lcm}$ 小于等于 $10^{18}$，设其为 $V$，故将所有方程分解后的 $p_i$ 的种类不会超过 $\log V$。所以我们可以遍历 $a$，两步分解质因数：第一步，使用之前分解出的质数来尝试分解，复杂度 $O(\log V)$。第二步，将第一步分解完后剩下的 $a_i$ 暴力分解，这一步单次 $O(\sqrt {a_i})$，但只会执行 $O(\log V)$ 次，在此题复杂度正好足够。
对于分解出来的质数 $p_i$，可能有多个对应的 $k_i$ 的模数，它们并不互质，但没关系，我们还有一个性质。
> 对于质数 $p$，正整数 $k_1<k_2$，若 $x \equiv b\ ({\rm mod}\ p^{k_2})$，则 $x \equiv b\ ({\rm mod}\ p^{k_1})$。
这个性质可以理解为，$x$ 在 $p$ 进制下，$x \equiv b\ ({\rm mod}\ p^{k})$ 相当于限制了 $x$ 的后 $k$ 位需要和 $b$ 相同，所以 $k$ 大时限制更强。
所以对于单个质数 $p_i$，我们只需要保留限制最强的也就是最大的 $k_i$ 对应的方程，如果这个方程和其它方程有矛盾，则说明方程组无解。
这样留下来的就是若干个不同的质数的次幂作为模数，它们互质，这时候就可以放心的使用 CRT 求解了！！
复杂度 $O(\sqrt{V_1}\log V_2+\log^2 V_2)$，其中 $V_1$ 为模数的值域，$V_2$ 为模数的 $\operatorname{lcm}$ 的值域，瓶颈在于质因数分解，如果使用高级的分解质因数算法，这个方法的使用范围可能能广一点。
我们不仅对 CRT 动了小手术，还对它动了两次手术！！！
经本人允许，代码也给出 Katyusha_01 的代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
void exgcd(long long a,long long b,long long& x,long long& y)
{
if(!b) return x = 1,y = 0,void();
exgcd(b,a % b,y,x),y -= a / b * x;
}
long long ny(long long a,long long mod)
{
a %= mod;
long long x,y;
exgcd(a,mod,x,y);
return (x % mod + mod) % mod;
}
int n;
long long a[100011],b[100011];
long long p[111],mod[111],rem[111],idx;
void Insert(long long& x,long long y,int i)
{
long long nmod = 1;
while(x % p[i] == 0)
x /= p[i],nmod *= p[i];
if(nmod > mod[i])
mod[i] = nmod,rem[i] = y % nmod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i] >> b[i];
for(int j = 1;j <= idx;j++)
Insert(a[i],b[i],j);
if(a[i] > 1)
{
for(long long np = 2;np * np <= a[i];np++) if(a[i] % np == 0)
p[++idx] = np,Insert(a[i],b[i],idx);
if(a[i] > 1)
p[++idx] = a[i],Insert(a[i],b[i],idx);
}
}
long long M = 1;
for(int i = 1;i <= idx;i++)
M *= mod[i];
long long ans = 0;
for(int i = 1;i <= idx;i++)
(ans += (__int128)(M / mod[i]) * ny(M / mod[i],mod[i]) % M * rem[i] % M) %= M;
cout << ans;
return 0;
}
```