IMO2026 vp

Day1

T1

• 设黑板上的 2026 个初始正整数构成的多重集为 $A = \{a_1, a_2, \dots, a_{2026}\}$。
• 设 $v_p(k)$ 表示整数 $k$ 的质因数分解中，质数 $p$ 的指数。特别地，如果 $p$ 不整除 $k$，则 $v_p(k) = 0$。对于数字 $1$，对任意质数 $p$ 都有 $v_p(1) = 0$。
• 设 $\Omega(k)$ 表示整数 $k$ 的所有质因数指数之和，即 $\Omega(k) = \sum_p v_p(k)$。规定 $\Omega(1) = 0$。

在每一步操作中，人类选择两个数 $m, n > 1$，并将它们替换为 $x$ 和 $y$，其中：

$$x = \gcd(m,n)$$ $$y = \frac{\text{lcm}(m,n)}{\gcd(m,n)}$$

考虑 $x$ 和 $y$ 对于任意质数 $p$ 的指数变化：

• $v_p(x) = \min(v_p(m), v_p(n))$
• $v_p(y) = v_p(\text{lcm}(m,n)) - v_p(\gcd(m,n)) = \max(v_p(m), v_p(n)) - \min(v_p(m), v_p(n)) = |v_p(m) - v_p(n)|$

操作后，这两个新数在质数 $p$ 上的指数之和变为

$$v_p(x) + v_p(y) = \min(v_p(m), v_p(n)) + |v_p(m) - v_p(n)| = \max(v_p(m), v_p(n))$$

---

(a)

令黑板上所有数字的 $\Omega$ 值总和为 $W$。在一次将 $m, n$ 替换为 $x, y$ 的操作中，$W$ 的变化量为

$$\Delta W = (\Omega(x) + \Omega(y)) - (\Omega(m) + \Omega(n)) = \sum_p \Big[ \max(v_p(m), v_p(n)) - (v_p(m) + v_p(n)) \Big]$$

容易知道 $\max(a, b) - (a + b) = -\min(a, b)$，因此

$$\Delta W = -\sum_p \min(v_p(m), v_p(n)) = -\Omega(\gcd(m,n))$$

分类讨论

1. $\gcd(m, n) > 1$ 此时 $\Omega(\gcd(m,n)) \ge 1$，所以 $\Delta W \le -1$。这意味着黑板上所有数字的质因数总数 $W$ 严格递减。
2. $\gcd(m, n) = 1$ 此时 $\Delta W = 0$，$W$ 保持不变。此时生成的新数为 $x = 1$ 和 $y = \frac{m \cdot n}{1} = m \cdot n$。
   因为人类选择的 $m, n$ 均严格大于 $1$，所以 $y = m \cdot n > 1$。
   在这个操作中，黑板上失去了两个大于 $1$ 的数（$m$ 和 $n$），增加了一个等于 $1$ 的数（$x$）和一个大于 $1$ 的数（$y$）。因此，黑板上大于 $1$ 的数字个数严格减少了 $1$ 个。

令 $N$ 为黑板上大于 $1$ 的数字个数。每次操作要么使 $W$ 严格减少，要么在 $W$ 不变的情况下使 $N$ 严格减少。由于 $W \ge 0$ 且 $N \ge 0$，这种状态变化不可能无限进行下去，因此操作必定在有限步内终止。

操作终止的条件是 $N < 2$。我们检查每次操作对 $N$ 的影响：每次拿走 $2$ 个大于 $1$ 的数，不管上述哪种情况，至少会放回 $1$ 个大于 $1$ 的数。因此，黑板上大于 1 的数字个数 $N$ 每次最多只会减少 1，绝不可能从 $N \ge 2$ 直接突变到 $N = 0$。所以，当操作因 $N < 2$ 而被迫终止时，必然有 $N = 1$。即黑板上恰好剩下一个大于 $1$ 的整数 $M$，且其余全是 $1$。

(b)

考虑任意一步操作，它将多重集 $S_p = \{v_p(a_1), \dots, v_p(a_{2026})\}$ 中的两个元素 $\alpha, \beta$ 替换为 $\min(\alpha, \beta)$ 和 $|\alpha - \beta|$。

• 设 $d$ 是替换前集合的公约数，则 $d | \alpha$ 且 $d | \beta$。显然 $d$ 也能整除 $\min(\alpha, \beta)$ 和 $|\alpha - \beta|$。所以 $d$ 也是替换后集合的公约数。
• 设 $d'$ 是替换后集合的公约数，则 $d' | \min(\alpha, \beta)$ 且 $d' | |\alpha - \beta|$。因为两数之和 $\min(\alpha, \beta) + |\alpha - \beta| = \max(\alpha, \beta)$，且已知 $d'$ 整除其中较小者，所以 $d'$ 必然同时整除 $\alpha$ 和 $\beta$。因此 $d'$ 也是替换前集合的公约数。

也就是说操作前后的最大公约数保持不变。

考虑计算 $M$。对于任意质数 $p$，初始状态下所有数字关于 $p$ 的指数集合的最大公约数为：
$$D_p = \gcd\big(v_p(a_1), v_p(a_2), \dots, v_p(a_{2026})\big)$$
当操作终止时，黑板上只有唯一的数 $M > 1$，其余 $2025$ 个数全是 $1$。因为 $v_p(1) = 0$，此时所有数字关于 $p$ 的指数构成的集合变为：
$$\{v_p(M), 0, 0, \dots, 0\}$$
又因为最大公约数是一个不变量，因此：
$$v_p(M) = D_p$$

这意味着最终数字 $M$ 的质因数分解中，每一个质数 $p$ 的指数 $v_p(M)$ 都完全由初始写在黑板上的数字唯一确定。$M = \prod_{p} p^{D_p}$ 是一个定值。

T2

这个题咱还不会

T3

这个题咱还没看

Day2

T1

这个题咱还没看

T2

这个题咱还没看

T3

这个题咱还没看