exCRT

CRT

  关于 $CRT$，主要的思想是这样的，对于一个方程组：

{ x ≡ a 1 ( m o d m 1 ) x ≡ a 1 ( m o d m 2 ) ⋮ x ≡ a n ( m o d m n )

⎩ ⎨ ⎧​x≡a1​(modm1​)x≡a1​(modm2​)⋮x≡an​(modmn​)​

  来说我们令：

$$m=\prod _{i=1}^n{m}_i,M_i=\frac{m}{m_i}$$

  然后求出 $M_i$ 在模 $m_i$ 意义下的乘法逆元 $t_i$，于是我们就得到了答案：

$$ans=\sum _{i=1}^n{a}_i{M}_i{t}_i$$

  在这里的计算步骤中，显然在计算逆元的时候要求 $\gcd (M_i,m_i)=1$，那么也就是要求 { m i } \{ m_i \} {mi​} l两两互质。

exCRT

总体思路

  扩展中国剩余定理就是要解决 $m_i$ 两两不互质的情况时解方程的方法。

  但是我们稍微经过一些思考就能发现，要想在 $CRT$ 的基础上小改一下来实现 $exCRT$ 时不可能的，因为如果 $\gcd (M_i,m_i)\ne 1$ 的话那么连逆元都不存在了，所以我们需要跳出 $CRT$ 的框架来思考怎样进行扩展。

  我们考虑合并两个方程，如果可以做到很快的合并，那么我们只需要一直合并下去再直接求解剩下的，唯一一个的，简单的，显然的，线性同余方程就能解决问题了。

合并

  考虑两个方程的合并：

{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 )

{x≡a1​(modm1​)x≡a2​(modm2​)​

  那么根据同余的性质我们就能得到：

$$x=k_1{m}_1+a_1=k_2{m}_2+a_2$$

  移一下项：

$$k_1{m}_1-k_2{m}_2=a_2-a_1$$

  这个式子的形式可能没有那么直观，所以我们令 $a=m_1,b=m_2,c=a_2-a_1,x=k_1,y=-k_2$，这个式子是不是就瞬间变成了这样：

$$ax+by=c$$

  这就是一个经典的不定方程求解的问题了，那么根据裴蜀定理，我们就能知道：

1. 如果 $\gcd (m_1,m_2)\mid (r_2-r_1)$，那么方程可以直接用 $exgcd$ 求出她的一组特殊解
2. 否则，方程无解

  那么我们求出 $x=k_1{m}_1+a_1$ 之后就得到了一个 $x$ 的特殊解同时满足这两个方程。我们给这个特殊解一个新的变量名 $X$。

  于是我们就可以愉快的构造新的方程了：

$$x\equiv X(\mathrm{mod}lcm(m_1,m_2))$$

  这个构造应该是非常显然的，因为 $x$ 与 $X$ 模 $m_1$ 同余且 $x$ 与 $X$ 模 $m_2$ 同余，那么 $x$ 与 $X$ 模 $lcm(m_1,m_2)$ 同余。

算法流程总结

1. 在所有方程中取两个出来
2. 合并（如果不能合并输出无解）
3. 只剩下一个方程直接解这唯一的一个方程得到答案

  完结撒花！！！

代码

#include
using namespace std;
#define int __int128
#define in read()
#define MAXN 100100

inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}
void write(int x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

int n = 0;
int a[MAXN] = { 0 };
int m[MAXN] = { 0 };

int k1 = 0, k2 = 0;
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 z = x; x = y, y = z - y * (a / b);
	return d;
}

signed main(){
	n = in; int ans = 0, lcm = 0;
	for(int i = 1; i <= n; i++) m[i] = in, a[i] = in;
	for(int i = 1; i < n; i++){
		k1 = 0, k2 = 0;
		int d = exgcd(m[i], m[i + 1], k1, k2);
		if((a[i + 1] - a[i]) % d != 0) { puts("-1"); return 0; }
		lcm = m[i] / d * m[i + 1];
		// 这里主义必须要先乘 (a[i + 1] - a[i]) 再除以 d
		// 因为有可能 k1 很小，先除以 d 就可能变成 0 然后再乘也没用了
		a[i + 1] = k1 * (a[i + 1] - a[i]) / d * m[i] + a[i];
		a[i + 1] = (a[i + 1] % lcm + lcm) % lcm; m[i + 1] = lcm;
	}
	int y = 0;
	exgcd(1, m[n], ans, y);
	write((ans * a[n] + m[n]) % m[n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50