exCRT

CRT

  关于 $CRT$,The main idea is this,for a system of equations：

$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1)\\ x\equiv a_1(\mathrm{mod}{m}_2)\\ ⋮\\ x\equiv a_n(\mathrm{mod}{m}_n)\end{array}$$

  Let's say we make：

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

  然后求出 $M_i$ 在模 $m_i$ 意义下的乘法逆元 $t_i$,So we got the answer：

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

  in the calculation step here,Obviously, when calculating the inverse element, it requires $\gcd (M_i,m_i)=1$,then the requirement $\{m_i\}$ l两两互质.

exCRT

总体思路

  Extending the Chinese remainder theorem is to solve $m_i$ Methods of Solving Equations When Pairs Are Not Coprime.

  But we can find out after a little thought,要想在 $CRT$ On the basis of small changes to achieve $exCRT$ impossible,因为如果 $\gcd (M_i,m_i)\ne 1$ If so, then the inverse element does not even exist.,So we need to jump out $CRT$ framework to think about how to scale.

  We consider combining the two equations,if it can be merged quickly,So we only need to continue to be merged to directly solve the rest,The only one,简单的,显然的,The linear congruence equation will solve the problem.

合并

  Consider the merger of two equations：

$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1)\\ x\equiv a_2(\mathrm{mod}{m}_2)\end{array}$$

  So we can get according to the nature of the congruence：

$$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$$

  The form of this formula may not be so intuitive,所以我们令 $a=m_1,b=m_2,c=a_2-a_1,x=k_1,y=-k_2$,Did this formula suddenly become like this?：

$$ax+by=c$$

  This is a classical indefinite equation solving problem.,Then according to Pei Shu's theorem,我们就能知道：

1. 如果 $\gcd (m_1,m_2)\mid (r_2-r_1)$,Then the equation can be directly used $exgcd$ find a set of special solutions for her
2. 否则,方程无解

  那么我们求出 $x=k_1{m}_1+a_1$ 之后就得到了一个 $x$ The special solution at the same time satisfy the two equations.We give this special solution a new variable name $X$.

  So we can happy new equations：

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

  This construction should be very obvious,因为 $x$ 与 $X$ 模 $m_1$ Congruence and $x$ 与 $X$ 模 $m_2$ 同余,那么 $x$ 与 $X$ 模 $lcm(m_1,m_2)$ 同余.

算法流程总结

1. Take two out of all equations
2. 合并（If you can't merge output without a solution）
3. There is only one equation left, directly solve the only one equation to get the answer

  完结撒花！！！

代码

#include<bits/stdc++.h>
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] = 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;
}