如果知道了原根的话这题就会简单很多
r是p的原根
\(r^a=x, r^b=y\)
那么$$r^{an} \equiv r^b (mod\ p) $$
根据原根的性质
\[an \equiv b(mod\ p-1)
\]
\[an-k(p-1)=b
\]
令n=p-1
由裴蜀定理得\((a,n)|b\)
\[ans=\sum_{a=1}^n \frac{n}{(n,a)}
\]
\[=\sum_{d|n}\frac{n}{d} \sum_{i=1}^n[(i,n)==d]
\]
\[=\sum_{d|n}\frac{n}{d} \sum_{i=1}^{\frac{n}{d}} [(i,\frac{n}{d})==1]
\]
\[=\sum_{d|n}d \varphi(d)
\]
那么最后这个直接dfs算即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1ll << 60;
const ll mo = 998244353;
ll n, ans, tot;
ll p[N], c[N];
void solve() {
ll mx = sqrt(n) + 1;
fo(i, 2, mx) {
if (n % i == 0) {
p[++tot] = i;
while (n % i == 0) {
c[tot]++;
n /= i;
}
}
}
if (n != 1) {
p[++tot] = n%mo;
c[tot] = 1;
}
}
void dfs(int x, ll y) {
if (x > tot) {
ans = (ans + y )%mo;
return;
}
dfs(x+1,y);
ll t=1;
fo(i,1,c[x]) {
dfs(x+1, y*t%mo*t%mo*p[x]%mo *(p[x]-1)%mo);
t=t*p[x]%mo;
}
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld", &n);
n--;
solve();
// fo(i,1,tot) printf("%lld %lld\n",p[i],c[i]);
ans = 1;
dfs(1, 1);
printf("%lld", ans);
return 0;
}