ABC335G - Discrete Logarithm Problems

题目链接

https://atcoder.jp/contests/abc335/tasks/abc335_g

题目大意

给定 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$ 和一个素数 $P$。求满足以下条件的二元组 $(i,j)$ 的个数。

• $1\le i,j\le N$ 。

• 存在正整数 $k$ ，使得 $A_i^k\equiv A_j(\mathrm{mod}P)$。

数据范围

• $1\le n\le 2\times {10}^5$
• $1\le a_i<P$
• $2<P\le {10}^{13}$ 且 $P$ 是素数

解题思路

考虑同余式 $x^k\equiv y(\mathrm{mod}P)$ 能推出什么结论。

令 ${\delta }_P(x)$ 表示 $x$ 在模 $P$ 意义下的阶，因为 $x^k$ 和 $y$ 在模 $P$ 意义下同余，所以一定有 ${\delta }_P(x^k)={\delta }_P(y)$ 。

其实以上的转化是我看题解看到的，至于应该怎么想才能自然地想到这一步，感觉需要一定的数学直觉，并且需要靠多做题积累经验。

根据阶的性质，有 ${\delta }_P(x^k)={\displaystyle \frac{{\delta }_P(x)}{gcd(k,{\delta }_P(x))}}$ ，所以可以得到 ${\delta }_P(x)=gcd(k,{\delta }_P(x))\cdot {\delta }_P(y)$ ，所以我们能推出一个必要条件

$$ $$\begin{array}{r}\mathrm{\exists }k\in \mathbb{N},x^k\equiv y(\mathrm{mod}P)⟹{\delta }_P(y)\mid {\delta }_P(x)\end{array}$$

$$

那么该条件的充分性是否成立呢。

• lemma 1

  如果 $ta\equiv tb(\mathrm{mod}tc)$ ，则 $a\equiv b(\mathrm{mod}c)$ 成立，其中 $t,a,b\in {\mathbb{N}}_{\mathbb{+}}$ 。

  证明非常简单，只需要把取模运算的表达式写出来即可证明。

假设 $g$ 为 $P$ 的一个原根，根据原根的性质，一定存在 $e_1$ 和 $e_2$ 使得 $g^{e_1}\equiv x(\mathrm{mod}P)$ ，$g^{e_2}\equiv y(\mathrm{mod}P)$，两边取离散对数有 $e_1\equiv {\mathrm{ind}}_g(x)(\mathrm{mod}P-1)$ ，$e_2\equiv {\mathrm{ind}}_g(y)(\mathrm{mod}P-1)$ 。我们要证 $\mathrm{\exists }k\in \mathbb{N},x^k\equiv y(\mathrm{mod}P)$ ，即证 $\mathrm{\exists }k\in \mathbb{N},k{e}_1\equiv e_2(\mathrm{mod}P-1)$ 。

根据条件有

$$ $$\begin{array}{r}{\delta }_P(y)\mid {\delta }_P(x)⟺{\delta }_P(g^{e_2})\mid {\delta }_P(g^{e_1})⟺{\displaystyle \frac{P-1}{gcd(e_2,P-1)}\mid {\displaystyle \frac{P-1}{gcd(e_1,P-1)}⟺gcd(e_1,P-1)\mid gcd(e_2,P-1)}}\end{array}$$

$$

令 $t=gcd(e_1,P-1)$ ，根据 lemma 1 和要证的式子 $k{e}_1\equiv e_2(\mathrm{mod}P-1)$ ，有

$$ $$\begin{array}{r}k\frac{e_1}{t}\equiv \frac{e_2}{t}(\mathrm{mod}\frac{P-1}{t})\end{array}$$

$$

因为 ${\displaystyle \frac{e_1}{t}}$ 与 ${\displaystyle \frac{P-1}{t}}$ 互质，所以有

$$ $$\begin{array}{r}k\equiv \frac{e_2}{t}\cdot {\left(\frac{e_1}{t}\right)}^{-1}(\mathrm{mod}\frac{P-1}{t})\end{array}$$

$$

所以条件的充分性成立，即

$$ $$\begin{array}{r}\mathrm{\exists }k\in \mathbb{N},x^k\equiv y(\mathrm{mod}P)⟹{\delta }_P(y)\mid {\delta }_P(x)\end{array}$$

$$

接下来，考虑如何求一个数 $a$ 在模 $P$ 意义下的阶 ${\delta }_P(a)$ 。因为 ${\delta }_P(a)\mid (P-1)$ ，并且若 ${\delta }_P(a)\mid b$ ，那么 $x^b\equiv 1(\mathrm{mod}P)$ 成立，所以可以先将 $P-1$ 质因数分解，初始时令 $b=P-1$ ，每次选取一个质因数 $p$ ，判断 $x^{\frac{b}{p}}\equiv 1(\mathrm{mod}P)$ 是否成立，成立则将 $p$ 除掉，不成立就取下一个质因数做相同的操作，这样最后得到的 $b$ 就是 $a$ 的阶。对于给定序列的每一个 $a_i$ 做一遍上述操作的时间复杂度为 $O(\sqrt{P}+n{\log }^{2}P)$ 。

根据上表，我们发现 $P-1$ 的约数个数的级别不超过 ${10}^4$ ，所以可以直接 $O(\mathrm{d}(P{)}^2)$ 计算 ${\delta }_P(a_i)$ 对答案的贡献。

所以总时间复杂度为 $O(\sqrt{P}+n{\log }^{2}P+\mathrm{d}(P{)}^2)$ ，时限为 $5\text{s}$ ，可以通过本题。

参考代码

https://atcoder.jp/contests/abc335/submissions/49356980