ABC212-G Power Pair の高速解法

ABC212-G Power Pair の素因数分解に $X(N)$ 時間かかるとしたときの $O(X(P-1) + \log(P))$ 解法を紹介します。

問題リンク

問題概要

$0 \le x, y \lt P$ を満たす $(x, y)$ の組であって、ある正整数 $n$ が存在して $x^ n \equiv y \pmod {P-1}$ を満たすものの個数 $\bmod {998244353}$ を求めよ。

問題変形

まず、ある素数 $P$ について原始根 $g$ がかならず $1$ つは存在する(参考)ことと、 $a, b$ のうちどちらかが $0$ ならばもう一方も $0$ でなければ条件が成り立たないことから、問題は次のように言い換えられます。

$0 \le a, b \lt P-1$ を満たす $(a, b)$ の組であって、ある正整数 $n$ が存在して $a \times n \equiv b \pmod {P-1}$ を満たすものの個数 $+\ 1\bmod {998244353}$ を求めよ。

本題

ここで、 $a$ を固定した時にありうる $b$ の個数は $\displaystyle\frac{P-1}{\gcd(a,P-1)}$ ですから、求めるものは $\displaystyle\sum_{a=0}^{P-2}\frac{P-1}{\gcd(a,P-1)}+1$ です。

この値は $\displaystyle \sum_{d|(P-1)} \left(\frac{P-1}{d} \times f\left(\frac{P-1}{d}\right)\right)+1$ に等しいです(ただし、 $f(x)$ は $\gcd(a,P-1)=x$ を満たす $a(0 \le a \lt P-1)$ の個数を表します)

ここで、 $f(x)$ について考えてみます。 $\gcd(a,P-1)=x$ を満たす $a(0 \le a \lt P-1)$ の個数は $\displaystyle\gcd\left(a',\frac{P-1}{x}\right)=1$ を満たす $\displaystyle a'\left(0 \le a' \lt \frac{P-1}{x}\right)$ の個数と等しく、またこの値は $\displaystyle\phi\left(\frac{P-1}{x}\right)$ ( $\phi(x)$ はオイラーのφ関数を表します)と等しいです。

これより、求める値は $\displaystyle \sum_{d|(P-1)} \left(\frac{P-1}{d} \times \phi\left(\frac{P-1}{d}\right)\right)+1$ です。

ここで、あとでわかりやすくするために $\displaystyle \sum_{d|(P-1)} (d \times \phi(d))+1$ と変形しておきます。

ところで、 $\phi(n)$ は $n$ が $\displaystyle \prod_{i=0}^{s-1} {p_i}^{e_i}$ ( $i \neq j$ ならば $p_i \neq p_j$ ) と表せるとき、次のように求められます。

$\displaystyle \phi(n)=\prod_{0 \le i \lt s \land e_i \neq 0} ({p_i}^{e_i} - {p_i}^{e_i-1})$

$n$ の約数はすべての $i$ について $0 \le t_i \lt e_i$ を満たす数列 $t$ を用いて $\displaystyle \prod_{i=0}^{s-1} {p_i}^{t_i}$ と表すことができ、またこの形で表現できるもののみが $n$ の約数です。

これらより、求めるものは $P-1 = \displaystyle \prod_{i=0}^{s-1} {p_i}^{e_i}$ として $\displaystyle \sum_{t_0=0}^{e_0} \sum_{t_1=0}^{e_1} \cdots \sum_{t_{s-1}=0}^{e_{s-1}} (\prod_{i=0}^{s-1} {p_i}^{t_i} \times \prod_{0 \le i \lt s \land t_i \neq 0} ({p_i}^{t_i}-{p_i}^{t_i-1}))+1$ です。これを整理して $\displaystyle \sum_{t_0=0}^{e_0} \sum_{t_1=0}^{e_1} \cdots \sum_{t_{s-1}=0}^{e_{s-1}} \prod_{0 \le i \lt s \land t_i \neq 0} ({p_i}^{t_i} \times ({p_i}^{t_i}-{p_i}^{t_i-1}))+1$ です。