原始根が絡む問題は時々出るイメージですね。
問題概要
素数 が与えられます。
次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。
- ある正の整数
が存在して、
が成立する
制約
は素数
考えたこと
整数問題ということで、とても面白そう!!
まずは として様子を見てみることにしました。各
を固定したときに、その冪乗としてありうるものを列挙すればよいことがわかります。
のとき
を列挙すると、
のとき
を列挙すると、
のとき
を列挙すると、
のとき
を列挙すると、
のとき
を列挙すると、
のとき
を列挙すると、
のとき
を列挙すると、
となる。こうしてみると、 は例外として、
を満たす最小の正の整数
を各 に対して合算すればよいことがわかります。なおこの
のことを
を法とした
の位数とよびます。「位数の総和を求めてください」というのが今回の問題の趣旨です。
なお、よく知られた Fermat の小定理は、次のようなものです。
このことから、 の位数は
以下であることがわかります。より詰めると、
を法とした
の位数
は
の約数である
ということがいえます。実際 のときも、
のいずれかになっています。
原始根
さて、Fermat の小定理を振り返ると、次のことが気になってきます。
「果たして位数が であるような
はあるのだろうか?」
実は、任意の素数 に対して、このような
が存在することが知られていて、
を法とした原始根とよびます。一般に原始根は複数個あります (後述するように
個あります)。たとえば
のときは、
の 2 つが原始根です。位数に関する問題を解くときは、原始根を考えることがしばしば有効です。
原始根は、その定義から次の面白い性質が導けます。
を
を法としたときの原始根 (の 1 つ) とすると、
を
で割ったあまりは、
をちょうど 1 つずつ行き渡る。
実際 ,
に対して、
の冪乗は
となって、
をちょうど 1 回ずつ行き渡ります。
この性質から、問題の条件である (
は例外視して除外します) は、
と書き直せることがわかります。このように で割ったあまりの世界を「原始根の指数」として書き直すと、見通しよくなることがよくあります!!!
原始根を用いて解析する
例として で考えてみます。原始根を
とします。このとき、
の冪乗の剰余を考えていくと、下表のようになります。ここで、
であることに注意しましょう。
下表から、 だけでなく、
も原始根になっていることがわかります。また、
の位数は、
の値と関係していることが見て取れるでしょう。
1 乗 | 2 乗 | 3 乗 | 4 乗 | 5 乗 | 6 乗 | 7 乗 | 8 乗 | 9 乗 | 10 乗 | 11 乗 | 12 乗 | 位数 | |
|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 | 1 |
|
|
|
|
|
|
|
6 | 2 | ||||||
|
|
|
|
|
4 | 3 | ||||||||
|
|
|
3 | 4 | ||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
12 | 1 |
|
|
|
2 | 6 | ||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
12 | 1 |
|
|
|
|
3 | 4 | |||||||||
|
|
|
|
|
4 | 3 | ||||||||
|
|
|
|
|
|
|
6 | 2 | ||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
12 | 1 |
表から一般に、
の位数は、
である
ということが見て取れます。このことは、初等整数論における次の性質から示せます ( と置き直しています)。
と
の最大公約数を
とするとき、
を
で割ったあまりは、
を 1 回ずつ行き渡る。
特に、 と
が互いに素であるとき、
を
で割ったあまりは、
を 1 回ずつ行き渡る。
このことの証明は次の記事を参照。
さて、 であるような
の個数は Euler 関数を用いて
と表せます。
なお Euler 関数 とは、「
のうち
と互いに素であるような整数の個数」と定義されます。
であるとき、
とすると、 となります。これを満たす
の個数は
となります。
以上をまとめると、今回の問題の答えは次のように表せます ( と書き直しています)。
求める組 の個数は、
である
計算量
まず の約数
をすべて列挙するのは
の計算量でできます。各
に関して Euler 関数
を計算するのは
でできます。よって
の約数の個数を
とすると、
の計算量で解けます。
未満の整数に対して
となります。一見すると
という計算量は少し厳しく見えますが、
が大きいような整数は素因子が大きい傾向にあり、その約数の Euler 関数はしばしば高速に計算できます。よって、愚直な
でも十分間に合いました。
より高速化する方法としては、
を素因数分解しておく (
- それによって
の各約数
に対して、
の最小の素因数
を求めておくことができる (
- それを用いると、各
に対する Euler 関数の値は「エラトステネスの篩を用いた高速素因数分解」と同じ要領で、
で計算できる
ということで、全体として へと改善することが考えられます。
コード
ここでは愚直な方法で実装します。
#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; }