AtCoder ABC #212 : G - Power Pair

今回から8問制。
https://atcoder.jp/contests/abc212/tasks/abc212_g

問題

素数Pが与えられる。
以下を満たす非負整数(x,y)の組は何通りか。

• x・yは0以上P未満
• x^n≡y となる正整数nが存在する

解法

x=0の時y=0一択である。以後、xが1以上のケースを考える。
適当な原始根を取り、X=log(x)、Y=log(y)とする。
その時、x^n≡yとなるのはX*n ≡ Y (mod (P-1))の時なので、GCD(X,P-1)=gの時、Yは(P-1)/g個の値を取りえることになる。

そこで、以下を求めよう。
f(k) := GCD(X,P-1)がkであるXの数
これは、
g(k) := GCD(X,P-1)がkの倍数であるXの数
を求めればそこから約数包除の要領で求めることができる。
あとはf(k)*(P-1)/kの総和を取ろう。

ll P;
const ll mo=998244353;
ll num[10101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P;
	P--;
	vector<ll> A;
	for(ll a=1;a*a<=P;a++) if(P%a==0) {
		A.push_back(a);
		if(a*a!=P) A.push_back(P/a);
	}
	sort(ALL(A));
	
	ll ret=1;
	for(i=A.size()-1;i>=0;i--) {
		num[i]=P/A[i];
		for(j=i+1;j<A.size();j++) if(A[j]%A[i]==0) num[i]-=num[j];
		(ret+=num[i]%mo*(P/A[i]%mo))%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

Fの方がしんどくない？