题意
求解下列同余方程组，
\[\begin{cases} b_1 x \equiv a_1 \pmod{m_1} \\ b_2 x \equiv a_2 \pmod{m_2} \\ \dots \\ b_n x \equiv a_n \pmod{m_n} \\ \end{cases}\]其中，\(n \leqslant 10^5, m_i \leqslant 10^8, lcm(m_i) \leqslant 10^{12}, a_i \leqslant 10^{12}, b_i \leqslant 10^6\)
Solution
不难发现，此方程组和exCRT模板有异曲同工之妙，尝试用相同的办法进行化简
考虑到exCRT的解产生的同余方程不带有前缀系数，考虑如下同余方程组，
\[\begin{cases} x \equiv a_1 \pmod{m_1} \\ bx \equiv a_2 \pmod{m_2} \\ \end{cases} \]展开得，
\[k_1 \times b m_1 - k_2 \times m_2= a_1 b - a_2 \]该式子左侧类似裴蜀定理， 则存在 \(\lambda_1, \lambda_2\) 满足 \(\lambda_1 \times b m_1 + \lambda_2 \times m_2= gcd(b m_1, m_2)\)
当 \(gcd(b m_1, m_2) \nmid a_1 b - a_2\) 时， 方程组无解.
当 \(gcd(b m_1, m_2) \mid a_1 b - a_2\) 时， 存在 \(k_1 , k_2\) 满足 \(k_1 \times b m_1 - k_2 \times m_2= a_1 b - a_2\).
则特解 \(x^* = \frac{a_1 b - a_2}{gcd(bm_1, m_2)} \times \lambda_1 \times m_1\)， 根据CRT的相关内容，得到通解
\[x = \frac{a_1 b - a_2}{gcd(bm_1, m_2)} \ \lambda_1 \ m_1 + k_1 \cdot lcm(m_1, m_2) \]考虑由多个同余方程组成的方程组，上面通解可表达成
\[x \equiv \frac{a_1 b - a_2}{gcd(bm_1, m_2)} \ \lambda_1 \ m_1 \pmod{lcm(m_1, m_2)} \]由此，从原方程组中依次选出一个同余方程进行合并，显然不失一般性。
考虑第一组方程如何求解，显然存在 \(x \equiv 0 \pmod{1}\) ，可用于求解第一个同余方程。
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
const int N = 1e5 + 50;
typedef long long lld;
inline lld read() {
register lld w = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return w * f;
}
multiset <lld> S;
int n, M;
lld m[N], a[N], b[N], atk[N];
inline lld gcd(lld a, lld b) {
return !b ? a : gcd(b, a % b);
}
inline lld exgcd(register lld a, register lld b, lld &x, lld &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
register lld d = exgcd(b, a % b, x, y);
register lld tmp = x;
x = y;
y = tmp - a / b * y;
return d;
}
inline lld mul(register lld a, register lld b, register lld p) {
lld ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}
lld a1, m1;
int main() {
int T = read();
while (T--) {
bool allone = 1;
n = read(), M = read();
S.clear();
for (register int i = 1; i <= n; ++i) a[i] = read();
for (register int i = 1; i <= n; ++i) {
m[i] = read();
if (m[i] != 1) allone = 0;
}
for (register int i = 1; i <= n; ++i) atk[i] = read();
for (register int i = 1; i <= M; ++i) {
register lld x = read();
S.insert(x);
}
for(int i = 1; i <= n; ++i) {
auto u = S.upper_bound(a[i]);
if(u != S.begin()) u--;
b[i] = *u;
S.erase(u);
S.insert(atk[i]);
}
if (allone) {
register lld maxa = 0;
for (register int i = 1; i <= n; ++i) maxa = max(maxa, (lld)ceil(1.0 * a[i] / b[i]));
printf("%lld\n", maxa);
continue;
}
a1 = 0;
m1 = 1;
for (register int i = 1; i <= n; ++i) {
lld x, y;
lld g = exgcd(mul(b[i], m1, m[i]), m[i], x, y);
x = (x % m[i] + m[i]) % m[i];
lld C = (a[i] - mul(b[i], a1, m[i]) + m[i]) % m[i];
if (C % g != 0) {
printf("-1\n");
goto ed;
}
lld tmp = m[i] / g * m1;
a1 = (a1 + mul(mul(C / g, x, m[i] / g), m1, tmp)) % tmp;
m1 = tmp;
}
printf("%lld\n", a1);
ed:;
}
return 0;
}
后记
最近写数学题全是bug
标签：gcd,lambda,NOI2018,register,times,equiv,屠龙,勇士,lld From： https://www.cnblogs.com/abigjiong/p/17555646.html