AtCoder Beginner Contest 212 G - Power Pair

放置している ABC - G, Ex を解き進めたい

問題へのリンク

問題

素数 $P$ が与えられる。

  • $ 0 \leq x \leq P - 1 $
  • $ 0 \leq y \leq P - 1 $
  • ある整数 $ n $ が存在して、$ x ^ n \equiv _ P y$

を満たす整数の組 $ (x, y) $ の個数を $ 998244353 $ で割った余りを求めよ。

前提

定義 $ 1 $（原始根）
整数 $ p $ に対し、$ r^0, r^1, \dots, r^{p-2} $ が相異なるような $ r \in (\mathbb{Z} / \mathbb{pZ}) ^ \times $ を $ p $ の原始根という。 すなわち、$ r $ は $ (\mathbb{Z} / \mathbb{pZ}) ^ \times $ の生成元である。
定理 $ 2 $
任意の素数に対し、原始根が存在する。

解法

$ x = 0 $ のとき、対応する $ y $ は $ 0 $ のみ。以降は $ x \neq 0 $ の場合を考える。

$ p $ の原始根を $ r $ とすると、ある整数 $ a, b $ を用いて $ x = r ^ a, ~ y = r ^ b $ と書ける。

$$ \begin{split} x ^ n \equiv _ P y &\iff r ^ {an} \equiv _ P r ^ b \\ &\iff an \equiv _ {P - 1} b \end{split} $$

なので、ある整数 $ n $ が存在して $ an \equiv _ {P - 1} b $ を満たすような $ (a, b) $ を数えればよい。

$ \mod P - 1 $ 上で $ \Brace{ka \mid k \in \mathbb{Z}} = \Brace{k\gcd(a, P - 1) \mid k \in \mathbb{Z}} $ が成り立つので、$ a $ を固定したとき、対応する $ b $ は $ \frac{P - 1}{\gcd(a, P - 1)} $ 個存在する。

$ \gcd(a, P - 1) $ ごとにまとめて数えることにすると、答えは

$$ \sum_{g \mid P - 1} \frac{P - 1}{g} \times \# \Brace{x \in \mathbb{Z}/(P-1)\mathbb{Z} \mid g = \gcd(x, P - 1)} $$

となる。

あとは $$ f(g) = \# \Brace{x \in \mathbb{Z}/(P-1)\mathbb{Z} \mid g = \gcd(x, P - 1)} $$ を求めれば終わり。 $$ \# \Brace{x \in \mathbb{Z}/(P-1)\mathbb{Z} \mid g \mid \gcd(x, P - 1)} = \sum_{g \mid h} f(h) $$ は簡単に計算できる（$ g $ の倍数の個数に等しい）ので、低速メビウス変換*1をすれば OK。

コード

https://atcoder.jp/contests/abc212/submissions/38687433

int main() {
    lint p;
    scanf("%lld", &p);
 
    vector<lint> ds;
    for (lint i = 1; i * i <= p - 1; ++i) {
        if ((p - 1) % i == 0) {
            ds.push_back(i);
            if (i * i != p - 1) {
                ds.push_back((p - 1) / i);
            }
        }
    }
    sort(ds.begin(), ds.end());
 
    mint dp[ds.size()];
    rrep(i, ds.size()) {
        dp[i] += (p - 1) / ds[i];
        rep(j, i) {
            if (ds[i] % ds[j] == 0) {
                dp[j] -= dp[i];
            }
        }
    }
 
    mint ans = 1;
    rep(i, ds.size()) { ans += dp[i] * ((p - 1) / ds[i]); }
    printf("%u\n", ans.val());
}

関連

*1:造語なので注意