0%

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