P8993 [北大集训 2021] 算术

Alex_Wei · 2023-08-07 10:47:46 · 题解

D4T1. P8993 [北大集训 2021] 算术

段数太多不方便考虑。从简化情况入手，考虑划分成 2 段，则原数可写为 b_1b ^ k + b_0。去掉 b_i\gets b_i\bmod p 对新数模 p 没有影响，所以可以认为新数为 b_0b - b_1，它和真正的新数模 p 相同。

考虑题目限制：

1. 若 b_1b ^ k + b_0 \equiv 0\pmod p，则 b_0b - b_1\equiv 0\pmod p。用加减消元法消去 b_0，得 b_1(b ^ {k + 1} + 1)\equiv 0\pmod p。因为 b_1 取 0\sim p - 1 任意值都可以，所以总存在 b_1\perp p。这说明 b ^ {k + 1} \equiv -1\pmod p。
2. 若 b_1b ^ k + b_0\equiv x\pmod p，则 b_0b - b_1\equiv y\pmod p，其中 x, y > 0。化简得 b_1(b ^ {k + 1} + 1)\equiv xb - y\pmod p，即 xb\equiv y\pmod p。这要求 1\sim p - 1 任意数乘以 b 后不是 p 的倍数。若 b\perp p 显然满足，否则令 x 为 \frac p {\gcd(b, p)} 即为反例。

综上，b\perp p 且 b ^ {k + 1}\equiv -1\pmod p。反过来可以证明若满足限制则 k 满足题目要求。

以段数为 3 为例：原数为 b_2 b ^ {2k} + b_1 b ^ k + b_0，新数为 b_0 b ^ 2 - b_1b + b_2。对于第一条限制，消元得 b_2 (b ^ {2k + 2} - 1) + b_1(b ^ {k + 2} + b)\equiv 0\pmod p。而 b ^ {k + 1} + 1\equiv 0\pmod p，且 b ^ {2k + 2} - 1 = (b ^ {k + 1} + 1) (b ^ {k + 1} - 1)，b ^ {k + 2} + b = (b ^ {k + 1} + 1) b。对于第二条限制，消元得 b_2 (b ^ {2k + 2} - 1) + b_1(b ^ {k + 2} + b) = x b ^ 2 - y，即要求 1\sim p - 1 任意数乘以 b ^ 2 后不是 p 的倍数。类似地，容易推出等价于 b\perp p。