算法
(原根) $O(\sqrt{P} + d^2)$
注意到,这里的 $P$ 是素数,所以 $P$ 一定有原根。
原根:
若整数 $m > 0$,$\gcd(g, m) = 1$,如果整数 $g$ 对 $m$ 的次数为 $\varphi(m)$,则 $g$ 叫做 $m$ 的一个原根。
定理 $1$:
设 $m > 1$,$m$ 有原根 $\Leftrightarrow$ $m$ 必为下列诸数之一:$2$,$4$,$p^l$,$2p^l$,这里 $p \geqslant 1$,$p$ 是奇素数。
缩系:
如果一个模数 $m$ 的剩余类里面的数与 $m$ 互素(显然,只需有一个与 $m$ 互素,其余的均与 $m$ 互素),就把它叫做
与 m 互素的剩余类
. 在与模数 $m$ 互素的全部剩余类中,各取一数所组成的集叫做模数 $m$ 的一组缩系
.
定理 $2$:
设 $\gcd(g, m) = 1$,$m > 0$,则 $g$ 是 $m$ 的一个原根的充要条件是 $g, g^2, \cdots, g^{\varphi(n)}$ 组成模数 $m$ 的一组缩系.
假设 $r$ 为模数 $P$ 的原根,对于 $\forall a, b \in [1, P - 1]$,若 $x \equiv r^a, \ y \equiv r^b \pmod P$,则 $x$ 与 $a$,以及 $y$ 与 $b$ 都是一一对应的。
于是我们可以得到
$$ x^n \equiv y \pmod P \Leftrightarrow r^{an} \equiv r^b \pmod P \Leftrightarrow an \equiv b \pmod {P - 1} $$
所以,原问题就转化成了求满足 $an \equiv b \pmod {P - 1}$ 的 $(a, b)$ 的个数。
我们可以通过以下这个式子得到:
$$ \sum_{a = 1}^{P - 1} \frac{P - 1}{\gcd(P - 1, a)} $$
但这个计算量是 $O(P)$
注意到 $P - 1$ 的约数数量大概是 $7000$ 左右,比较少,所以我们可以枚举 $g$ $\Big(\text{其中}g = \gcd(P - 1, a)\Big)$
$\frac{P - 1}{\gcd(P - 1, a)}$ 就变成了 $\frac{P - 1}{g} \cdot f(g)$,其中 $f(g)$ 表示满足 $g = \gcd(P - 1, a)$ 的 $a$ 的个数
记 $d$ 为 $P - 1$ 的约数个数,先令 $f(g) = \frac{P - 1}{g}$,然后通过 $f(g) = f(g) - f(g\ \text{除自身外的倍数})$ 算出最终的 $f(g)$,计算量为 $O(d^2)$
$$ \begin{aligned} \sum\limits_{a = 1}^{10} {\frac{{10}} {{\gcd \left( {10,a} \right)}}} &= \frac{{10}} {{\gcd \left( {10,1} \right)}} + \frac{{10}} {{\gcd \left( {10,2} \right)}} + \frac{{10}} {{\gcd \left( {10,3} \right)}} + \frac{{10}} {{\gcd \left( {10,4} \right)}} + \frac{{10}} {{\gcd \left( {10,5} \right)}} \\\ &+ \frac{{10}} {{\gcd \left( {10,6} \right)}} + \frac{{10}} {{\gcd \left( {10,7} \right)}} + \frac{{10}} {{\gcd \left( {10,8} \right)}} + \frac{{10}} {{\gcd \left( {10,9} \right)}} + \frac{{10}} {{\gcd \left( {10,10} \right)}} \\\ &= \frac{{10}} {1} + \frac{{10}} {2} + \frac{{10}} {1} + \frac{{10}} {2} + \frac{{10}} {5} + \frac{{10}} {2} + \frac{{10}} {1} + \frac{{10}} {2} + \frac{{10}} {1} + \frac{{10}} {{10}} \\\ &= 4 \times \frac{{10}} {1} + 4 \times \frac{{10}} {2} + 1 \times \frac{{10}} {5} + 1 \times \frac{{10}} {{10}} \end{aligned} $$
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using std::cin;
using std::cout;
using std::map;
using std::vector;
using ll = long long;
using mint = modint998244353;
int main() {
ll n;
cin >> n;
--n;
vector<ll> ds, ps;
{ // n 的约数
for (ll i = 1; i * i <= n; ++i) {
if (n % i) continue;
ds.push_back(i);
if (i * i != n) ds.push_back(n / i);
}
}
{ // n 的素因数分解
ll x = n;
for (ll i = 2; i * i <= x; ++i) {
if (x % i) continue;
ps.push_back(i);
while (x % i == 0) x /= i;
}
if (x != 1) ps.push_back(x);
}
sort(ds.begin(), ds.end());
map<ll, mint> dp;
for (ll d : ds) dp[d] = n / d;
for (ll p : ps) {
for (ll d : ds) {
if (d % p == 0) dp[d / p] -= dp[d];
}
}
mint ans = 1;
for (ll d : ds) ans += dp[d] * (n / d);
cout << ans.val() << '\n';
return 0;
}
+v+