中国剩余定理

中国剩余定理

讲解

对于这种类型的方程组，求一个合法的(x)

[egin{cases} x≡a_1 pmod {r_1}\ x≡a_2 pmod {r_2}\ x≡a_3 pmod {r_3}\ ...\ x≡a_n pmod {r_n} end{cases}]

其中(r_1,r_2,r_3,...,r_n)互质，这就是中国剩余定理解决的问题

其实我们可以直接构造出一个特殊解

令(A_i=prod_{j e i}r_j)，因为各个(r_i)互质，所以(A_i)与(r_i)也是互质的，所以一定存在一个(c_i)，使得(c_i*A_i\% r_i=1)

令(x_i=c_i*A_i*a_i)，则(x_i\% r_i=a_i,x_i\% r_j=0|j e i)

这意味着什么？把所有的(x_i)加起来就是我们要求的解(x)了！

令(R=prod_{i=1}^{n}r_i)，对于任意一个解(x)，我们将其加上(R)的任意倍数也同样成立

通解为：

(x=sum_{i=1}^{n}c_i*A_i*a_i+p*R)

其中(p)为任意整数

代码

求(c_i)相当于求(A_i)的逆元，但是由于(r_i)不一定是质数，只是和(A_i)互质而已，所以不能用快速幂求，要用扩欧

void exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b) x = 1,y = 0;
	else
	{
		exgcd(b,a%b,y,x);
		y -= a/b*x;
	}
}
LL CRT()
{
	LL s = 1,ret = 0;
	for(int i = 1;i <= n;++ i) s *= r[i];
	for(int i = 1;i <= n;++ i)
	{
		LL x,y;
		exgcd(s/r[i],r[i],x,y);
		x = (x + r[i]) % r[i];
		ret = (ret + a[i] * (s / r[i]) % s * x % s) % s;
	}
	return ret;
}

扩展中国剩余定理

讲解

扩展中国剩余定理是用来解决(r_i)各自不互质的情况的问题

对于扩展中国剩余定理，它所做的事情其实是将两个方程不断合并，最后剩下一个方程即可得出最终解

假设我们要合并的两个方程为：

[egin{cases} x≡a_1 pmod {r_1}\ x≡a_2 pmod {r_2} end{cases}]

我们的目标是将其合并成(x≡? pmod {lcm(r_1,r_2)})的形式

我们可将两个方程化为：(x=a_1+s_1*r_1=a_2+s_2*r_2)，其中(s_1,s_2)为整数

将其移项可得(s_1*r_1-s_2*r_2=a_2-a_1)

我们可以通过扩欧求得一组特解((s_1',s_2'))，当然如果无解就可以直接在这里判断了

然后我们就可以得到(s_1)的通解(s_1=s_1'+k*(r_2/gcd(r_1,r_2)))，所以为了防爆，我们在求出(s_1')之后也可以对其取模(r_2/gcd(r_1,r_2))

然后我们将(s_1)代回原方程，可得(x=a_1+(s_1'+k*(r_2/gcd(r_1,r_2)))*r_1=a_1+s_1'*r_1+k*lcm(r_1,r_2))

我们即可得到方程(x≡a_1+s_1'*r_1 pmod{lcm(r_1,r_2)})

代码

void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(!b) d = a,x = 1,y = 0;
	else
	{
		exgcd(b,a%b,d,y,x);
		y -= a/b*x;
	}
}
LL exCRT()
{
	for(int i = 1;i < n;++ i)
	{
		LL x,y,d;
		exgcd(r[i],r[i+1],d,x,y);
		if((a[i+1] - a[i]) % d) return -1;
		x = ((a[i+1] - a[i]) / d * x % (r[i+1] / d) + r[i+1] / d) % (r[i+1] / d);
		LL lcm = r[i] * r[i+1] / d;
		a[i+1] = (x * r[i] % lcm + a[i]) % lcm;
		r[i+1] = lcm;
	}
	return a[n];
}