当前位置：首页 > news >正文

26-4-23日志 - Ghost

news 2026/4/23 23:10:52

今日 Keyword：
Part 1. ExGCD.
1. WriteUp.
2. Tips.
T1. LOJ #10209. 「一本通 6.4 例 1」青蛙的约会 / 洛谷 P1516.
1. WriteUp.
Part 2. 中国剩余定理 CRT.
1. Lemma1
2. Proof.
T2. LOJ #10212. 「一本通 6.4 例 4」曹冲养猪 / 洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
1. WriteUp.
今日总结：

P.S.今天是挑战150天冲击CSP-S 2026省一的第3天，目前阶段：数论.
离CSP-S 2026 还有148天.

“纵有疾风起，人生不言弃”

今日 Keyword：

ExGCD,乘法逆元,中国剩余定理（CRT）.

Part 1. ExGCD.

昨天我们成功解决了「如何用ExGCD解决形如 \(ax + by = gcd(a,b)\) 的方程的问题」，那么今天我们进行一个推广：
Subtask1: 求形如 \(ax + by = c\) 的整数解。

WriteUp.

那么显然我们要应用昨天的结论做转化，设存在 \(x',y',a',b'\) ,
\(s.t. a'x' + b'y' = 1\) ，根据昨天的推导，这个方程有解的充要条件就是 \(gcd(a',b') = 1\) .
接下来我们考虑转化，令 \(a' = \frac{a}{g} ,b' = \frac{b}{g} ,c' = \frac{c}{g} ,g = gcd(a,b)\) ,
就有：
\(a'x'c' + b'y'c' = c'\) ，更进一步， \(a'x'c'g + b'y'c'g = c'g\) .
也就等于 \(ax'c' + by'c' = c\) ，即 \(x = x'c',y = y'c'\) 是一组特解。
易知有解的充要条件是 \(gcd(a,b) | c\) .
因此，我们只需要用ExGCD求出方程 \(a'x + b'y = 1\) 的一组解，最后乘上 \(\frac{c}{gcd(a,b)}\) 即可。
而由昨天的推导，最小正整数解就是 \(x = (x_0 mod \frac{b}{g} + \frac{b}{g}) mod \frac{b}{g}\) .

Tips.

有人要说了，我们可以解 \(ax' + by' = 1\) ，两边直接同乘一个 \(c\) 就可以得到想要的答案。
事实上，我一开始也是这么想的，然而这是不正确的，理由如下：
我们不保证 \(a,b\) 互质，因此这个转化后的方程可能无解。
构造中的 \(a' = \frac{a}{g} ,b' = \frac{b}{g} ,c' = \frac{c}{g} ,g = gcd(a,b)\) 就是确保子方程的 \(a,b\) 互质的。
因此有且仅有这么一种解法，当然，这也告诉我们，当 \(a,b\) 互质时，这个结论正确。

另外的一种理解方法，若是 \(a,b\) 互质，\(g = 1\)，等价于这种思路。

T1. LOJ #10209. 「一本通 6.4 例 1」青蛙的约会 / 洛谷 P1516.

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止.
但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 \(0\) 度处为原点，由东往西为正方向，单位长度 \(1\) 米，这样我们就得到了一条首尾相接的数轴。
设青蛙 A 的出发点坐标是 \(x\)，青蛙 B 的出发点坐标是 \(y\)。青蛙 A 一次能跳 \(m\) 米，青蛙 B 一次能跳 \(n\) 米，两只青蛙跳一次所花费的时间相同。
纬度线总长 \(L\) 米。现在要你求出它们跳了几次以后才会碰面。

输入只包括一行五个整数 \(x,y,m,n,L\)。

输出碰面所需要的次数，如果永远不可能碰面则输出一行一个字符串 `Impossible`。

对于 \(100\%\) 的数据，\(1 \le x, y, m, n \le 2 \times 10^9\)，\(x \ne y\)，\(1 \le L \le 2.1 \times 10^9\)。

WriteUp.

不妨设跳了 \(T\) 步，那么A的新坐标就是 \((x + Tm)\) ，B的新坐标就是 \((y + Tn)\) .
相遇的充要条件为 \(存在k \in Z , (x + Tm) - (y + Tn) = kL\) .
变形得 \((n - m)T + kL = x - y\) .
用ExGCD求解即可。

#include <bits/stdc++.h>
using namespace std;
long long x, y, n, m, l;
void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {if (b == 0) {d = a, x = 1, y = 0;} else {exgcd(b, a % b, d, x, y);long long t = x;x = y, y = t - (a / b) * y;}
}
long long gcd(long long a, long long b) {if (b == 0)return a;return gcd(b, a % b);
}
int main() {cin >> x >> y >> m >> n >> l;if (n < m) {swap(n, m);swap(x, y);}long long g = gcd(n - m, l);if ((x - y) % g != 0 || n == m) {cout << "Impossible" << endl;return 0;}long long ax = (n - m) / g, bx = (l) / g, cx = (x - y) / g;long long d = 0, tx = 0, ty = 0;exgcd(ax, bx, d, tx, ty);cout << ((tx * cx) % bx + bx) % bx << endl;return 0;
}

Tips: 警惕符号错误！

Part 2. 中国剩余定理 CRT.

Lemma1

\[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{cases}\]

其中 \(m_1, m_2, \dots, m_n\) 两两互质。则方程组在模 \(M = m_1 m_2 \cdots m_n\) 下有唯一解：

\[x \equiv \sum_{i=1}^{n} a_i \cdot M_i \cdot t_i \pmod{M} \]

其中 \(M_i = M / m_i\)，\(t_i\) 是 \(M_i\) 模 \(m_i\) 下的逆元，即 \(M_i \cdot t_i \equiv 1 \pmod{m_i}\)

Proof.

因为 \(M_i\) 是除 \(m_i\) 之外所有模数的倍数，所以：
\(\forall k!=i, a_iM_it_i \equiv 0 \pmod{m_k}\)

以及：
\(\forall i \in n, a_iM_it_i \equiv a_i \pmod{m_i}\)
现在直观地理解，将 \(x\) 带入原式后，由于取模的性质，对于所有 \(k!=i\) 的项，取模后均为0.
因此，只剩下 \(a_iM_it_i\) 这一项，又因为 \(M_it_i \equiv 1 \pmod{m_i}\) ，所以， \(a_i \equiv a_i \pmod{m_i}\) .
Qed.

有解的充要条件即是模数两两互质，否则，在上述证明过程中，消去多余项的这一步就不成立，会有多余的项留下。

T2. LOJ #10212. 「一本通 6.4 例 4」曹冲养猪 / 洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。
举个例子，假如有 \(16\) 头母猪，如果建了 \(3\) 个猪圈，剩下 \(1\) 头猪就没有地方安家了。如果建造了 \(5\) 个猪圈，但是仍然有 \(1\) 头猪没有地方去，然后如果建造了 \(7\) 个猪圈，还有 \(2\) 头没有地方去。
你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

第一行包含一个整数 \(n\) —— 建立猪圈的次数，接下来 \(n\) 行，每行两个整数 \(a_i, b_i\)，表示建立了 \(a_i\) 个猪圈，有 \(b_i\) 头猪没有去处。你可以假定 \(a_1 \sim a_n\) 互质。

输出包含一个自然数，即为曹冲至少养母猪的数目。

\(1 \leq n\le10\)，\(0 \leq b_i\lt a_i\le100000\)，\(1 \leq \prod a_i \leq 10^{18}\)

WriteUp.

中国剩余定理CRT 模版题。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;const int MAXN = 15;  
ll a[MAXN], m[MAXN], Mx[MAXN];
ll M = 1, n;void exgcd(ll a, ll b, ll& d, ll& x, ll& y) {if (b == 0) {d = a; x = 1; y = 0;} else {exgcd(b, a % b, d, x, y);ll t = x;x = y;y = t - (a / b) * y;}
}void CRT() {ll ans = 0;ll tx, ty, td;for (int i = 1; i <= n; i++) {exgcd(Mx[i], m[i], td, tx, ty);tx = (tx % m[i] + m[i]) % m[i];i128 term = (i128)a[i] * Mx[i] % M * tx % M;ans = (ans + (ll)term) % M;}cout << (ans + M) % M << endl;
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> m[i] >> a[i];M *= m[i];}for (int i = 1; i <= n; i++) {Mx[i] = M / m[i];}CRT();return 0;
}