【luogu P4777】【模板】扩展中国剩余定理(EXCRT)(数论)

【模板】扩展中国剩余定理(EXCRT)

题目链接:luogu P4777

题目大意

给你一些条件,要你找最小的 x,使得满足它被一些数取模的答案是要求的数。
模数不一定互质。
【luogu P4777】【模板】扩展中国剩余定理(EXCRT)(数论)

思路

不会 CRT 的自己先看看 CRT 怎么写。(点我查看)

不难想到,前面我们是将式子的答案选可以加载一起的直接加在一起。
但你不难想到你搞逆元的时候可能会没有逆元,因为模数与你要逆元的数可能并不互质。

那要怎么搞呢?我们重新考虑如何合并两条式子:
x ≡ c 1 (   m o d     m 1 ) x\equiv c_1(\bmod\ m_1) x≡c1​(mod m1​)
x ≡ c 2 (   m o d     m 2 ) x\equiv c_2(\bmod\ m_2) x≡c2​(mod m2​)
那首先很显然的是我们设 M = lcm ( m 1 , m 2 ) M=\text{lcm}(m_1,m_2) M=lcm(m1​,m2​),如果有解,那一定是合并成这样:
x ≡ c 3 (   m o d     M ) x\equiv c_3(\bmod\ M) x≡c3​(mod M)
那我们继续设 t = gcd ⁡ ( m 1 , m 2 ) t=\gcd(m_1,m_2) t=gcd(m1​,m2​),那根据我们可以得到这两个式子:
c 3 = c 1 + a × m 1 ( 0 ⩽ a < M / m 1 ) c_3=c_1+a\times m_1(0\leqslant a< M/m_1) c3​=c1​+a×m1​(0⩽a<M/m1​)
c 3 = c 2 + b × m 2 ( 0 ⩽ b < M / m 2 ) c_3=c_2+b\times m_2(0\leqslant b< M/m_2) c3​=c2​+b×m2​(0⩽b<M/m2​)
(后面 a a a 的范围后面的限制 M / m 1 M/m_1 M/m1​ 也可以写成 m 2 / t m_2/t m2​/t)
( b b b 也同理)

那接着两个式子相等:
c 1 + a × m 1 = c 2 + b × m 2 c_1+a\times m_1=c_2+b\times m_2 c1​+a×m1​=c2​+b×m2​
c 2 − c 1 = a × m 1 − b × m 2 c_2-c_1=a\times m_1-b\times m_2 c2​−c1​=a×m1​−b×m2​
因为 t = gcd ⁡ ( m 1 , m 2 ) t=\gcd(m_1,m_2) t=gcd(m1​,m2​) 所以 a × m 1 − b × m 2 a\times m_1-b\times m_2 a×m1​−b×m2​ 只能表示 t t t 的倍数。( a , b a,b a,b 是你要求的)
所以有解的条件就是 t ∣ ( c 2 − c 1 ) t|(c_2-c_1) t∣(c2​−c1​)

那接着你想,你要把 a , b a,b a,b 其中一个消掉,就可以求另一个了。
那要怎么消呢?用取模。
你会发现前面有一个 a < M / m 1 a<M/m_1 a<M/m1​,而且它也可以写成 m 2 / t m_2/t m2​/t。
那你发现你把前面的式子都除以 t t t:
( c 2 − c 1 ) / t = a × m 1 / t − b × m 2 / t (c_2-c_1)/t=a\times m_1/t-b\times m_2/t (c2​−c1​)/t=a×m1​/t−b×m2​/t
然后再对 m 2 / t m_2/t m2​/t 取模,就有了 ( c 2 − c 1 ) / t ≡ a × m 1 / t (   m o d     ( m 2 / t ) ) (c_2-c_1)/t\equiv a\times m_1/t(\bmod\ (m_2/t)) (c2​−c1​)/t≡a×m1​/t(mod (m2​/t))
那就只剩 a a a 了,我们搞一下,就有了:
a = inv ( m 1 / t , m 2 / t ) × ( c 2 − c 1 ) / t   m o d   ( m 2 / t ) a=\text{inv}(m_1/t,m_2/t)\times(c_2-c_1)/t\bmod(m_2/t) a=inv(m1​/t,m2​/t)×(c2​−c1​)/tmod(m2​/t)

然后把 a a a 带入回 c 3 = c 1 + a × m 1 c_3=c_1+a\times m_1 c3​=c1​+a×m1​ 就可以了。

然后由于数据规模是 1 0 18 10^{18} 1018,用乘法都会爆炸,那我们就用黑科技并不龟速的龟速乘。
然后不开 long long 见祖宗——我 是 傻 逼。

代码

#include<cstdio>
#define ll long long

using namespace std;

int n;
ll a[100001], b[100001];

ll ksc(ll x, ll y, ll mo) {
	x %= mo;
	y %= mo;
	ll c = (long double)x * y / mo;
	long double re = x * y - c * mo;
	if (re < 0) re += mo;
		else if (re >= mo) re -= mo;
	return re;
}

ll gcd(ll x, ll y) {
	if (!y) return x;
	return gcd(y, x % y);
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll re = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return re;
}

ll inv(ll a, ll mo) {
	ll x, y;
	exgcd(a, mo, x, y);
	x = (x % mo + mo) % mo;
	return x;
}

int main() {
//	freopen("read.txt", "r", stdin);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld %lld", &a[i], &b[i]);
	
	for (int i = 2; i <= n; i++) {
		ll t = gcd(a[1], a[i]);
		ll M = a[i] / t * a[1];
		ll A = ksc(inv(a[1] / t, a[i] / t), (b[i] - b[1]) / t, a[i] / t);
		b[1] = ((b[1] + ksc(A, a[1], M)) % M + M) % M;
		a[1] = M;
	}
	
	printf("%lld", b[1]);
	
	return 0;
}
上一篇:做题记录 Luogu P1168


下一篇:【Luogu】P4916 [MtOI2018]魔力环 题解