题解：P9929 [NFLSPC #6] 挑战大数因子分解

· · 题解

比较基础的数论板子。很难不发现，通过公开信息即可解出 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)