「校内模拟20200429C」游戏达人

给定 $p,A,B,C,D$，求 $x,y$ 满足 $C^x \equiv D^y \pmod x$，并最小化 $Ax + By$。

$6000$ 组询问，$0 \leq A,B,C,D,p \leq 10^9$，保证 $p$ 是质数。

题解（个人做法）

因为 $p$ 是质数，我们求出其原根 $g$，故

$$C^x \equiv D^y (\bmod\ p) \Leftrightarrow{} g^{cx} \equiv g^{dy} (\bmod\ p) \Leftrightarrow{} cx \equiv dy (\bmod\ \varphi(p))$$

假设

$$f(x,p,A,B) = \min \{ A(ix \bmod p) + Bi \mid i \}$$

我们转化为了一个稍微好计算一点的问题：$f(d \cdot c^{-1}, p-1, A, B)$。

当然，可能存在 $c$ 模 $\varphi(p) = p-1$ 没有逆元的情况，我们需要做一点处理：

1 2 3 4 5 6

# c x \equiv d y \pmod p g = gcd(c, d, p) c /= g; d /= g; p /= g cg = gcd(c, p); c /= cg; b *= cg dg = gcd(d, p); d /= dg; a *= dg p /= cg * dg

考虑如何计算 $f$，采用类似欧几里得的思想。

$$f(x,p,A,B) = \begin{cases} \small\text{直接 }O(1)\small\text{ 计算} & (x = 0) \\ f(x / \gcd(x,p), p / \gcd(x,p), A \gcd(x,p), B) & (x \not\perp p) \\ f(x \bmod p, p, A, B) & (x \geq p) \\ f(q, x, \frac {Ap} x, \frac {Ax + B} x) & \text{otherwise} \\ \end{cases}$$

假设 $i = \tfrac {kp + b} x$，其中 $x \mid kp + b$。由于 $x \perp p$，故确定 $b$ 后就能唯一确定 $k$。

实际上 $k$ 满足：

$$\begin{aligned} kp + b &\equiv 0 & \pmod x \\ k &\equiv b \cdot (-p^{-1}) & \pmod x \\ \end{aligned}$$

令 $q \equiv -p^{-1} \pmod x$，那么原式可以化为：

$$\begin{aligned} f(x,p,A,B) &= \min\{ A(ix \bmod p) + Bi \mid i \} \\ &= \min\{ A((kp + b) \bmod p) + B \cdot \tfrac {kp + b} x \mid i \} \\ &= \min\{ Ab + B \cdot \tfrac {(pq \bmod p) \cdot p + b} {x} \mid i \} \\ &= f(q, x, \tfrac {Bp} {x}, \tfrac {Ax + B} {x}) \\ \end{aligned}$$

感性理解了一下逆元的分布应该是比较随机的，感觉复杂度应该是 $O(\log n)$。

题解（标答做法）

类欧几里得推导，设：

$$g(a,b,c,d,e,f) = \min_i \left( a + b i + c \left\lfloor \frac {di + e} {f} \right\rfloor \right)$$

若 $d \geq f$，假设 $d = gf + h$，则

$$\begin{aligned} g(a,b,c,d,e,f) &= \min_i \left( a + bi + c \left\lfloor \frac {(gf + h) i + e} {f} \right\rfloor \right) \\ &= \min_i \left( a + (b+cg) i + c \left\lfloor \frac {hi + e} {f} \right\rfloor \right) \\ &= g(a, b + cg, c, h, e, f) \\ &= g(a, b + c \lfloor d/f \rfloor, c, d \bmod f, e, f) \\ \end{aligned}$$

若 $d < f$，则

$$\begin{aligned} g(a,b,c,d,e,f) &= \min_j \min_i \left( a + bi + c j \left[ \left\lfloor \frac {di + e} {f} \right\rfloor \geq j\right] \right) \\ \end{aligned}$$

其中

$$\begin{aligned} \left[ \left\lfloor \frac {di + e} {f} \right\rfloor \geq j\right] &= \left[ \frac {di + e} {f} \geq j \right] \\ &= \left[ i \geq \frac {jf - e} {d} \right] \\ &= \left[ i > \frac {jf - e - 1} {d} \right] \\ &= \left[ i > \left\lfloor \frac {jf - e - 1} {d} \right\rfloor \right] \\ \end{aligned}$$

因为我们要求最小化，不妨直接令 $\displaystyle i = \left\lfloor \frac {jf - e - 1} {d} \right\rfloor +1$

故

$$\begin{aligned} g(a,b,c,d,e,f) &= \min_j \left( a + b \left( \left\lfloor \frac {jf - e - 1} {d} \right\rfloor +1 \right) + cj \right) \\ &= g(a+b,c,b,f,-e-1,d) \\ \end{aligned}$$

其实 $c$ 是不需要存的，但是式子都推好了就懒得改了。

另外还要存一下枚举的上下界，一层递归是 $7$ 个参数。

细节

0x01

特判 $p = 2$ 的情况。

0x02

$$ka \equiv kb \pmod p$$

两边能同时除以 $k$ 当且仅当

1. $k \perp p$，转化为 $a \equiv b \pmod p$
2. $k \mid p$，转化为 $a \equiv b \pmod {(p/k)}$