RainAir
My OI Blog
RainAir
「ZROI851」exexBSBSGSGS

题意:求$a^x \equiv b(\mod p^e)$ 的最小整数解。
$3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$,询问不超过 $1000$ 组。

暴力分跑 bsgs 其实就可以了…因为保证了 $(a,p^e) = 1$。
但是这样显然会 T,于是我们就不要往 bsgs 的方面去想了。
我们考虑 $p$ 很小并且 $>2$,这就强烈暗示我们使用原根解离散对数了。
首先关于原根有一点小性质:
1. $2,4,p^e,2p^e$ 都有原根
2. $p$ 和 $p^e$ 有相同的原根。

所以我们就可以通过暴力找出原根了,接下来我们对两边取 $log$。
$$(log_ga)x \equiv log_gb (\mod \varphi(p^e))$$

考虑我们如果能求出 $(log_ga)$ 和 $(log_gb)$ 的话,我们就代入解一个同余方程就好了。我们考虑求 $(log_ga)$:设 $x = log_ga$,将其化为指数形式:
$$g^x \equiv a (\mod p^e)$$
(我们需要注意如果对指数取模就要用欧拉定理加上 $\varphi$,如果是对整个数取模就要用原来的模数)
首先一个直观的想法就是使用 bsgs (那和暴力有什么区别)所以我们考虑如何利用质数比较小的这一特性来计算。
考虑我们如果已经计算出下式:
$$g^x \equiv a(\mod p^i)$$
尝试是否能快速推到 $\mod p^{i+1}$ 的形式。我们考虑用模数上的指数给指数方程编号(例如上式的编号是 $i$),那么我们考虑第 $i$ 个质数方程解出的解满足 $x \equiv x_i (\mod \varphi(p^i))$。而我们现在想要得到新解 $x \equiv x_{i+1} (\mod \varphi(p^{i+1}))$。注意观察这两个解的规律,不难发现 $x_{i+1} \equiv x_i (\mod \varphi(p^i))$ 即 $x_{i+1} = x_i+k\varphi(p^i)$。
我们枚举这个 $k$ 然后检验答案即可。不难发现 $k$ 的数量只有 $O(p)$ 个。
所以我们这样一层层迭代下去就可以了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/714
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「ZROI851」exexBSBSGSGS
题意:求$a^x \equiv b(\mod p^e)$ 的最小整数解。 $3 < p \leq 50,p^e \leq 10^18,a\nmid p,b \nmid p$,询问不超过 $1000$ 组。 暴力分跑 bsgs 其实就可以了...因为保证了 $(a,p^e)…
扫描二维码继续阅读
2019-07-21
标签
近期评论