原始根が絡む問題は時々出るイメージですね。

問題へのリンク

問題概要

素数 $P$ が与えられます。

次の条件を満たす整数 $(x, y)$ の組の個数を 998244353 で割ったあまりを求めてください。

$0 \le x \le P - 1$
$0 \le y \le P - 1$
ある正の整数 $n$ が存在して、 $x^{n} \equiv y \pmod P$ が成立する

制約

$2 \le P \le 10^{12}$
$P$ は素数

考えたこと

整数問題ということで、とても面白そう！！

まずは $P = 7$ として様子を見てみることにしました。各 $x$ を固定したときに、その冪乗としてありうるものを列挙すればよいことがわかります。

$x = 0$ のとき $y$ を列挙すると、 $0$
$x = 1$ のとき $y$ を列挙すると、 $1$
$x = 2$ のとき $y$ を列挙すると、 $2, 4, 1$
$x = 3$ のとき $y$ を列挙すると、 $3, 2, 6, 4, 5, 1$
$x = 4$ のとき $y$ を列挙すると、 $4, 2, 1$
$x = 5$ のとき $y$ を列挙すると、 $5, 4, 6, 2, 3, 1$
$x = 6$ のとき $y$ を列挙すると、 $6, 1$

となる。こうしてみると、 $x = 0 (y = 0)$ は例外として、

$x^{e} \equiv 1 \pmod P$ を満たす最小の正の整数 $e$

を各 $x$ に対して合算すればよいことがわかります。なおこの $e$ のことを $P$ を法とした $x$ の位数とよびます。「位数の総和を求めてください」というのが今回の問題の趣旨です。

なお、よく知られた Fermat の小定理は、次のようなものです。

$x^{P-1} \equiv 1 \pmod P$

このことから、 $x$ の位数は $P-1$ 以下であることがわかります。より詰めると、

$P$ を法とした $x$ の位数 $e$ は $P-1$ の約数である

ということがいえます。実際 $P = 7$ のときも、 $e = 1, 2, 3, 6$ のいずれかになっています。

原始根

さて、Fermat の小定理を振り返ると、次のことが気になってきます。

「果たして位数が $P-1$ であるような $x$ はあるのだろうか？」

実は、任意の素数 $P$ に対して、このような $x$ が存在することが知られていて、 $P$ を法とした原始根とよびます。一般に原始根は複数個あります (後述するように $\varphi(P-1)$ 個あります)。たとえば $P = 7$ のときは、 $3, 5$ の 2 つが原始根です。位数に関する問題を解くときは、原始根を考えることがしばしば有効です。

原始根は、その定義から次の面白い性質が導けます。

$r$ を $P$ を法としたときの原始根 (の 1 つ) とすると、

$r^{0}, r^{1}, r^{2}, \dots, r^{P-2}$ を $P$ で割ったあまりは、 $1, 2, \dots, P-1$ をちょうど 1 つずつ行き渡る。

実際 $P = 7$ , $r = 3$ に対して、 $3$ の冪乗は $1, 3, 2, 6, 4, 5$ となって、 $1, 2, ..., 6$ をちょうど 1 回ずつ行き渡ります。

この性質から、問題の条件である $x = 1, 2, \dots, P-1$ ( $x = 0$ は例外視して除外します) は、

$x = r^{0}, r^{1}, r^{2}, \dots, r^{P-1}$

と書き直せることがわかります。このように $P$ で割ったあまりの世界を「原始根の指数」として書き直すと、見通しよくなることがよくあります！！！

原始根を用いて解析する

例として $P = 13$ で考えてみます。原始根を $r$ とします。このとき、 $r^{a}$ の冪乗の剰余を考えていくと、下表のようになります。ここで、 $r^{12} \equiv 1 \pmod P$ であることに注意しましょう。

下表から、 $r$ だけでなく、 $r^{5}, r^{7}, r^{11}$ も原始根になっていることがわかります。また、 $r^{a}$ の位数は、 ${\rm gcd}(a, P - 1)$ の値と関係していることが見て取れるでしょう。

$r^{a}$	1 乗	2 乗	3 乗	4 乗	5 乗	6 乗	7 乗	8 乗	9 乗	10 乗	11 乗	12 乗	位数	${\rm gcd}(a, P-1)$
$r$	$r$	$r^{2}$	$r^{3}$	$r^{4}$	$r^{5}$	$r^{6}$	$r^{7}$	$r^{8}$	$r^{9}$	$r^{10}$	$r^{11}$	$1$	12	1
$r^{2}$	$r^{2}$	$r^{4}$	$r^{6}$	$r^{8}$	$r^{10}$	$1$							6	2
$r^{3}$	$r^{3}$	$r^{6}$	$r^{9}$	$1$									4	3
$r^{4}$	$r^{4}$	$r^{8}$	$1$										3	4
$r^{5}$	$r^{5}$	$r^{10}$	$r^{3}$	$r^{8}$	$r$	$r^{6}$	$r^{11}$	$r^{4}$	$r^{9}$	$r^{2}$	$r^{7}$	$1$	12	1
$r^{6}$	$r^{6}$	$1$											2	6
$r^{7}$	$r^{7}$	$r^{2}$	$r^{9}$	$r^{4}$	$r^{11}$	$r^{6}$	$r$	$r^{8}$	$r^{3}$	$r^{10}$	$r^{5}$	$1$	12	1
$r^{8}$	$r^{8}$	$r^{4}$	$1$										3	4
$r^{9}$	$r^{9}$	$r^{6}$	$r^{3}$	$1$									4	3
$r^{10}$	$r^{10}$	$r^{8}$	$r^{6}$	$r^{4}$	$r^{2}$	$1$							6	2
$r^{11}$	$r^{11}$	$r^{10}$	$r^{9}$	$r^{8}$	$r^{7}$	$r^{6}$	$r^{5}$	$r^{4}$	$r^{3}$	$r^{2}$	$r$	$1$	12	1

表から一般に、

$r^{a}$ の位数は、 $\frac{P-1}{{\rm gcd}(a, P-1)}$ である

ということが見て取れます。このことは、初等整数論における次の性質から示せます ( $Q = P-1$ と置き直しています)。

$a$ と $Q$ の最大公約数を $g$ とするとき、 $a, 2a, 3a, \dots, \frac{Q}{g} a$ を $Q$ で割ったあまりは、 $0, g, 2g, \dots, (Q-1)g$ を 1 回ずつ行き渡る。

特に、 $a$ と $Q$ が互いに素であるとき、 $a, 2a, 3a, \dots, Qa$ を $Q$ で割ったあまりは、 $0, 1, 2, \dots, Q-1$ を 1 回ずつ行き渡る。

このことの証明は次の記事を参照。

qiita.com

さて、 ${\rm gcd}(a, P-1) = g$ であるような $a$ の個数は Euler 関数を用いて $\varphi(\frac{P-1}{g})$ と表せます。

なお Euler 関数 $\varphi(N)$ とは、「 $1, 2, \dots, N$ のうち $N$ と互いに素であるような整数の個数」と定義されます。 ${\rm gcd}(a, P-1) = g$ であるとき、

$a = ga'$
$P-1 = gb'$

とすると、 ${\rm gcd}(a', b') = 1$ となります。これを満たす $a'$ の個数は $\varphi(b') = \varphi(\frac{P-1}{g})$ となります。

以上をまとめると、今回の問題の答えは次のように表せます ( $d = \frac{P-1}{g}$ と書き直しています)。

求める組 $(x, y)$ の個数は、

$\sum_{d | P-1} d \varphi(d) + 1$

である

計算量

まず $P-1$ の約数 $d$ をすべて列挙するのは $O(\sqrt{P})$ の計算量でできます。各 $d$ に関して Euler 関数 $\varphi(d)$ を計算するのは $O(\sqrt{P})$ でできます。よって $P-1$ の約数の個数を $D$ とすると、 $O(D\sqrt{P})$ の計算量で解けます。

$10^{12}$ 未満の整数に対して $D \le 6720$ となります。一見すると $O(D\sqrt{P})$ という計算量は少し厳しく見えますが、 $D$ が大きいような整数は素因子が大きい傾向にあり、その約数の Euler 関数はしばしば高速に計算できます。よって、愚直な $O(D \sqrt{P})$ でも十分間に合いました。

より高速化する方法としては、

$P-1$ を素因数分解しておく ( $O(\sqrt{P})$
それによって $P-1$ の各約数 $d$ に対して、 $d$ の最小の素因数 $p$ を求めておくことができる ( $O(\sqrt{P})$
それを用いると、各 $d$ に対する Euler 関数の値は「エラトステネスの篩を用いた高速素因数分解」と同じ要領で、 $O(\log P)$ で計算できる

ということで、全体として $O(\sqrt{P} + D \log P)$ へと改善することが考えられます。

コード

ここでは愚直な方法で実装します。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

// 約数列挙
vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

// Euler 関数
long long Euler(long long N) {
    long long N2 = N;
    for (long long p = 2; p * p <= N2; ++p) {
        if (N2 % p == 0) {
            N = N / p * (p - 1);
            while (N2 % p == 0) {
                N2 /= p;
            }
        }
    }
    if (N2 != 1) N = N / N2 * (N2 - 1);
    return N;
}
 
int main() {
    long long P;
    cin >> P;
    auto div = calc_divisor(P-1);
 
    long long res = 1;
    for (auto d: div) {
        long long tmp = (Euler(d) % MOD) * (d % MOD) % MOD;
        res += tmp;
    }
    cout << res % MOD << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 212 G - Power Pair (黄色, 600 点)

問題概要

制約

考えたこと

原始根

原始根を用いて解析する

計算量

コード