ABC 212 G
直接做不好做，考虑将 \(x,y\) 替换成某个幂的形式来试图去掉底数。
记 \(g\) 为 \(P\) 的原根，那么 \(x,y\) 一定可以表示成 \(g\) 的某个在模意义下的幂，不妨设 \(x \equiv g^{i} (\bmod P),y \equiv x^{j}(\bmod P)\)。
那么原限制就变为了 \(g^{i \times n} \equiv g^{j} (\bmod P)\)。显然等价于 \(i \times n \equiv j (\bmod P-1)\)，这个由原根的定义可以得到。
答案即为
\[\sum\limits_{i=0}^P \sum\limits_{j=0}^P [\exists n,i \times n \equiv j (\bmod P-1)]
\]
右边的式子又等价于询问 \(i \times n + (P-1) \times m =j\) 这个方程是否有正整数解。由裴蜀定理我们知道只有当 \(\gcd(i,P-1) | j\) 的时候存在正整数解。
由于 \(i=0,j=0\) 的情况较为特殊，将他提出来单独写。
\[\sum\limits_{i=1}^P \sum\limits_{j=1}^P [\gcd(i,P-1) | j] +1
\]
也就是
\[\sum\limits_{i=1}^{P-1} \frac{P-1}{\gcd(i,P-1)} + 1
\]
考虑枚举 \(\gcd(i,P-1)\)
\[\sum\limits_{d=1}^{P-1} \lfloor \frac{P-1}{d} \rfloor \sum\limits_{i=1}^{\large \lfloor \frac{P-1}{d}\rfloor} [\gcd(i,\lfloor \frac{P-1}{d} \rfloor)=1]
\]
等价于
\[\sum\limits_{d=1}^{P-1} \lfloor \frac{P-1}{d} \rfloor \phi(\lfloor \frac{P-1}{d} \rfloor)
\]
我一开始化简到这里就开始无脑杜教筛了，但是后面发现只有当 \(d | P-1\) 的时候答案才有效，所以直接暴力计算即可。只要好好写 \(\phi\) 就是可以过的。
注意 \(\phi(i)\) 是有可能 \(\ge mod\) 的，取模的时候要注意。
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define vi vector<int>
#define pb(x) push_back(x)
#define pii pair<int,int>
#define lowbit(x) x&-x
using namespace std;
const int mod=998244353;
ll ans;
int n,m,T;
inline int read(){
int s=0,f=0;
char ch=getchar();
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return f?-s:s;
}
inline int phi(int x){
int res=x;
for(register int i=2;i*i<=x;++i){
if(x%i==0){
while(x%i==0) x/=i;
res=res/i*(i-1);
}
}
if(x>1) res=res/x*(x-1);
return res%mod;
}
signed main(){
n=read()-1;
for(register int i=1;i*i<=n;++i){
if(n%i) continue;
ans=(ans+i*phi(i)%mod)%mod;
if(i*i!=n) ans=(ans+(n/i%mod)*phi(n/i)%mod)%mod;
}
cout<<ans+1;
return 0;
}