Atcoder 212G Power Pair

Problem Statement

Given is a prime number (P).

How many pairs of integers ((x,y))satisfy the following conditions?

(0≤x≤P−1)
(0≤y≤P−1)
There exists a positive integer (n) such that (x^n≡y(modP))

Since the answer may be enormous, print it modulo 998244353.

Constraints

(2≤P≤10^12)
(P is a prime number.)

Input

Input is given from Standard Input in the following format:

Output

Print the answer modulo 998244353.

Sample Input 1 Copy

Copy

Sample Output 1 Copy

Copy

Four pairs ((x,y)=(0,0),(1,1),(2,1),(2,2))satisfy the conditions.

Sample Input 2 Copy

Copy

Sample Output 2 Copy

Copy

Sample Input 3 Copy

Copy

998244353

Sample Output 3 Copy

Copy

329133417

题目翻译

给定质数(P),求满足(0≤x≤P−1)和(0≤y≤P−1)，且(x^n≡y(modP))的方案数，答案对998244353取模

题目解析

首先是本题显然可以考虑原根

假设原根为(G),那么(x,y)可以写成(G^a,G^b)，原方程变成(an=b(mod P-1))

假设枚举(a),求(b)的方案数。((a,b))有解当(gcd(P-1,a)|b)

所以(b)的方案数为(frac{P-1}{gcd(P-1,a)}),总方案数为(sum_{a=1}^{P-1}frac{P-1}{gcd(P-1,a)})

但是(O(P))的复杂度不能通过(P<=10^{12})

考虑到存在很多的(a)，(gcd(P-1,a))的值相同。因为(P-1)的因数个数为(O(sqrt{P-1})),所以(gcd(P-1,a))的值只有(O(sqrt{n}))个

考虑枚举(P-1)的因数，令(g=gcd(P-1,a))，答案为(sum_{g}frac{P-1}{g}*φ(frac{P-1}{g}))

这里(φ(x))不适用(O(P))的线性筛，可以通过推导式：

(φ(n)=n(1-frac{1}{d_1-1})...(1-frac{1}{d_k-1}))

预处理(O(sqrt{P-1}))。令(P-1)因数数为(d)，求总方案复杂度为(O(d^2))

P.S:根据官方题解，小于(10^{12})因数最多的数是963761198400，有6720个因数。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
ll P;
ll fac[2000005],ans;
int cnt,Mod=998244353;
void getFactor(){
    for (ll i=1;i<=sqrt(P);i++){
        if (P%i==0){
            fac[++cnt]=i;
            if (P/i!=i)
                fac[++cnt]=P/i;
        }
    }
}
ll getPhi(ll n){
    ll phi=n;
    for (ll i=2;i<=sqrt(n);i++){
        if (n%i==0){
            phi=phi/i*(i-1);
            while (n%i==0) n/=i;
        }
    }
    if (n>1) phi=phi/n*(n-1);
    return phi%Mod;
}
int main(){
    cin>>P;
    P--;
    getFactor();
    for (int i=1;i<=cnt;i++){
        ans=(ans+(P/fac[i])%Mod*getPhi(P/fac[i])%Mod)%Mod;
    }
    cout<<ans+1;//考虑x=0,y=0
}