【BZOJ1319】Discrete Roots


题意

求 \(x^k\equiv a(mod\; p)\) 中所有满足要求的 \(x\) 。

分析

考虑求一个 \(p\) 的原根 \(g\) ,则一定有 \(x\equiv g^y(mod \; p),a\equiv g^z(mod\; p)\) 。

对于 \(a\equiv g^z(mod\; p)\) ,可以直接通过拓展 BSGS 求得一个满足要求的 \(z\) 。

根据 \(x\equiv g^y(mod \; p),a\equiv g^z(mod\; p)\) ,我们有 \(x^k\equiv g^{ky}\equiv g^z (mod \; p)\) 。

因为原根是有周期的,且周期为 \(p-1\) ,于是有 \(ky\equiv z(mod \; (p-1))\) 。

这个可以通过拓展 GCD 解一个 \(y\) 出来,显然我们就可以得到一个特解 \(x\equiv g^y(mod \; p)\) 。

现在要求的所有的解,我们可以通过不断的向上调整 \(y\) 来得到所有的 \(x\) ,显然这也是有周期的,可以直接用 set 维护。

这样最后遍历 set 输出就好了。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,993

Categories

Archive

Comments