[洛谷P4777]【模板】扩展中国剩余定理（EXCRT）

题目大意：给你一些关于$x$的方程组：
$$
\begin{cases}
x\equiv a_1\pmod{mod_1}\\
x\equiv a_2\pmod{mod_2}\\
\vdots\\
x\equiv a_n\pmod{mod_n}
\end{cases}
$$
求解$x$的最小非负整数解（$\gcd(mod_1,mod_2,\cdots,mod_n)\not=1$）

题解：$EXCRT$，假设有两个方程
$$
\begin{cases}
x\equiv x_1\pmod{A}\\
x\equiv x_2\pmod{B}
\end{cases}\\
设g=\gcd(A,B),k=\left\lfloor\dfrac xg\right\rfloor,c=x\bmod g\\
x=kg+c\\
所以x_1\equiv x_2\equiv c\pmod g\\
\begin{cases}
kg+c\equiv x_1\pmod A\\
kg+c\equiv x_2\pmod B\\
\end{cases}\\
令k_1=\left\lfloor\dfrac {x_1}g\right\rfloor,k_2=\left\lfloor\dfrac {x_2}g\right\rfloor\\
\begin{cases}
kg+c\equiv k_1g+c\pmod A\\
kg+c\equiv k_2g+c\pmod B\\
\end{cases}\\
\begin{cases}
kg\equiv k_1g\pmod A\\
kg\equiv k_2g\pmod B\\
\end{cases}\\
\begin{cases}
k\equiv k_1\pmod{\left\lfloor\dfrac Ag\right\rfloor}\\
k\equiv k_2\pmod{\left\lfloor\dfrac Bg\right\rfloor}\\
\end{cases}\\
这样就可以用CRT解决了
$$
$CRT$部分见博客

卡点：无

C++ Code：

#include <cstdio>

long long gcd(const long long a, const long long b) {

	if (!b) return a;

	return gcd(b, a % b);

}

inline long long lcm(const long long a, const long long b) { return a / gcd(a, b) * b; }

inline long long mul(const long long x, const long long y, const long long mod) {

	static long long res;

	res = x * y - static_cast<long long> (static_cast<long double> (x) * y / mod + 0.5) * mod;

	return res + (res >> 63 & mod);

}

void exgcd(const long long a, const long long b, long long &x, long long &y) {

	if (!b) x = 1, y = 0;

	else exgcd(b, a % b, y, x), y -= a / b * x;

}

inline long long inv(const long long a, const long long mod) {

	static long long x, y;

	exgcd(a, mod, x, y);

	return x + (x >> 63 & mod);

}

inline long long getreduce(const long long x, const long long mod) { return x + (x >> 63 & mod); }

long long CRT(const long long A, const long long mod1, const long long B, const long long mod2) {

	const long long mod = mod1 * mod2, inv1 = inv(mod1, mod2);

	return getreduce(mul(mul(getreduce((B - A) % mod2, mod2), inv1, mod2), mod1, mod) + A, mod);

}

long long EXCRT(const long long A, const long long mod1, const long long B, const long long mod2) {

	if (A % mod2 == B) return A;

	const long long GCD = gcd(mod1, mod2), t = CRT(A / GCD, mod1 / GCD, B / GCD, mod2 / GCD);

	return t * GCD + (A % GCD);

}

int n;

int main() {

	scanf("%d", &n);

	long long LCM = 1, ans = 0;

	for (int i = 0; i < n; ++i) {

		static long long a, b;

		scanf("%lld%lld", &a, &b); b %= a;

		ans = EXCRT(ans, LCM, b, a);

		LCM = lcm(LCM, a);

	}

	printf("%lld\n", ans);

}

巴特西

[洛谷P4777]【模板】扩展中国剩余定理（EXCRT）

最新文章

热门文章