UyHiP-2013-Jun

被 Matrix67 抢了先机，本来我还想来篇“最新题解”呢。

看起来是 first solver ……感觉不错。把题目给 fanhq 看了下，和我一样的做法。

Problem

只允许使用加、减、模运算，10 次操作内求出 \[f(x) = 1 + x + x^2 + x^4 \mod{2233393}\]

Solution

首先我们先给出一个九次操作的解法。

注意到 \(x^2 = M^2 \mod{(M+x)}\) 。如果保证 \(x^2 < M+x\) ，那么我们就有 \(x^2 = (M^2 \mod{(M+x)})\) 。为了保证 \(M\) 足够大，我们先令 \(x\) 模 \(p = 2233393\) ，这样 \(x < p\) ，令 \(M = p^2\) 即可。这样一次平方操作需要两次操作，共需要两次平方操作，三次加法，最后再来一次模，一开始要令 \(x\) 模 \(p\) ，共 9 次操作。

其实这个方法蛮好的，但总感觉有点怪怪的——为啥不把两次平方操作以及加法全部预处理呢？

易得 \[-M \equiv x \mod{(M + x)}\] 我们有 \[f(-M) \equiv f(x) \mod{(M+x)}\] 注意到 \(f(-M)\) 是常数，且当 \(M+x > f(x)\) 时，我们有 \(f(x) = f(-M) \mod{(M+x)}\) 。为方便起见，我们可以直接令 \(M = f(p)\) ，于是我们就只需要四次操作：

m = f(p)
fm = f(-m)
def f(x) :
    return fm % (m + x % p) % p