自动搬运

查看原文

来自洛谷，原作者为

	Moeebius µ || blog.moeebius.top || 是微渺/的希望/我们依然前行

搬运于2025-08-24 22:53:07，当前版本为作者最后更新于2024-11-13 16:41:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

比较基础的数论板子。很难不发现，通过公开信息即可解出 $S_4P=S_3-S_5, S_6=2S_5-S_3$。由于 PolarSea 的解密方式中用到了 $P$，而我们只有 $S_4P$，自然可以想着去观察 $C$ 模 $S_4P$ 的值。

$$\begin{aligned} C&=(S_3-S_5)^3w+MS_5+r(S_3-S_5) \\ &= S_4^3P^3w + MS_4P + MS_6 + rS_4P \\ &= kS_4P + MS_6 \end{aligned} $$

由于输入合法，$C=kS_4P+MS_6$ 这一方程必然有解，令 $v = \gcd(S_4P, S_6)$，将 $C, S_4P, S_6$ 均除以 $v$，得到了一个形如 $ax + by = c\ (\gcd(a,b)=1)$ 的不定方程。

由于满足题目要求的解唯一，使用 exgcd 解出在 $(S_1, S_7)$ 范围内的解即可。

为了避免写高精度，可以使用 python。

import sys
sys.setrecursionlimit(int(1e7))
sys.set_int_max_str_digits(int(1e7))

def exgcd(a, b):
	if b == 0:
		return (1, 0, a)
	(x1, y1, v) = exgcd(b, a % b)
	return (y1, x1 - (a // b) * y1, v)

(s3, s5, s7, s1) = map(int, input().strip().split(' ')) # 截至发稿时，本题数据中仍存在行末空格
C = int(input())

s4p = s3 - s5
s6 = 2 * s5 - s3

(k, M, v) = exgcd(s4p, s6)

C //= v
s4p //= v
s6 //= v

ans = (M % s4p + s4p) % s4p * C

if (ans <= s1):
	ans += (s1 - ans + s4p) // s4p * s4p
if (ans >= s7):
	ans -= (ans - s7 + s4p) // s4p * s4p

print(ans)