G - Power Pair(数论、推式子)
题意
给定质数P，求有多少个x，y满足：
- 0 ≤ x , y ≤ P − 1 0 \leq x, y \leq P-1 0≤x,y≤P−1
- ∃ n ∈ N , x n ≡ y ( m o d P ) ∃n∈N,x^{n}≡y(mod \ P) ∃n∈N,xn≡y(mod P)
分析
由题意可知，就是要求 ∑ x = 0 P − 1 ∑ y = 0 P − 1 [ ∃ n ∈ N , x n ≡ y ( m o d P ) ] \sum_{x=0}^{P-1}\sum_{y=0}^{P-1}[∃n∈N,x^{n}≡y(mod \ P)] ∑x=0P−1∑y=0P−1[∃n∈N,xn≡y(mod P)]，那么就尝试把这个式子化简一下，得到一个比较容易求的式子。
不难观察出当 x = 0 x=0 x=0时，只有 y = 0 y=0 y=0满足题意，所以可以化简为：
a n s = ∑ x = 0 P − 1 ∑ y = 0 P − 1 [ ∃ n ∈ N , x n ≡ y ( m o d P ) ] = 1 + ∑ x = 1 P − 1 ∑ y = 1 P − 1 [ ∃ n ∈ N , x n ≡ y ( m o d P ) ] \begin{align} ans&=\sum_{x=0}^{P-1}\sum_{y=0}^{P-1}[∃n∈N,x^{n}≡y(mod \ P)]\\ &=1+\sum_{x=1}^{P-1}\sum_{y=1}^{P-1}[∃n∈N,x^{n}≡y(mod \ P)] \end{align} ans=x=0∑P−1y=0∑P−1[∃n∈N,xn≡y(mod P)]=1+x=1∑P−1y=1∑P−1[∃n∈N,xn≡y(mod P)]
因为P是素数，所以除0外 [ 1 , P − 1 ] [1,P-1] [1,P−1]中所有的数都是原根，得到 ∀ k ∈ N + , 1 ≤ k ≤ P − 1 , ∃ n ∈ N , 1 ≤ n ≤ P − 1 , g n ≡ k ( m o d P ) ∀k∈N^{+}, 1≤k≤P−1,∃n∈N, 1≤n≤P−1,g^{n}≡k(mod \ P) ∀k∈N+,1≤k≤P−1,∃n∈N,1≤n≤P−1,gn≡k(mod P),设 x = g a x=g^{a} x=ga， y = g b y=g^{b} y=gb，可得
a n s = 1 + ∑ a = 1 P − 1 ∑ b = 1 P − 1 [ ∃ n ∈ N + , g a n ≡ g b ( m o d P ) ] \begin{align} ans=1+\sum_{a=1}^{P-1}\sum_{b=1}^{P-1}[∃n∈N^{+},g^{an}≡g^{b}(mod \ P)] \end{align} ans=1+a=1∑P−1b=1∑P−1[∃n∈N+,gan≡gb(mod P)]
根据欧拉定理， g x m o d p g^{x}mod \ p gxmod p的循环节为 ϕ ( P ) = P − 1 \phi(P)=P-1 ϕ(P)=P−1,因此可得
a n s = 1 + ∑ a = 1 P − 1 ∑ b = 1 P − 1 [ ∃ n ∈ N + , a n ≡ b ( m o d P − 1 ) ] \begin{align} ans=1+\sum_{a=1}^{P-1}\sum_{b=1}^{P-1}[∃n∈N^{+},an≡b(mod \ P-1)] \end{align} ans=1+a=1∑P−1b=1∑P−1[∃n∈N+,an≡b(mod P−1)]
根据裴蜀定理， g c d ( a n , p − 1 ) ∣ b gcd(an,p-1)|b gcd(an,p−1)∣b, a n = b + t ∗ ( P − 1 ) an=b+t*(P-1) an=b+t∗(P−1), k ∈ N + , b = k ∗ g c d ( a n , P − 1 ) k∈N^{+},b=k*gcd(an,P-1) k∈N+,b=k∗gcd(an,P−1)
a n s = 1 + ∑ a = 1 P − 1 ∑ b = 1 P − 1 [ g c d ( a , P − 1 ) ∣ b ] = 1 + ∑ a = 1 P − 1 ∑ k = 1 ∞ [ k ≤ P − 1 g c d ( a , P − 1 ) ] = 1 + ∑ a = 1 P − 1 P − 1 g c d ( a , P − 1 ) \begin{align} ans&=1+\sum_{a=1}^{P-1}\sum_{b=1}^{P-1}[gcd(a,P-1)|b]\\ &=1+\sum_{a=1}^{P-1}\sum_{k=1}^{\infty}[k \leq \frac{P-1}{gcd(a,P-1)}]\\ &=1+\sum_{a=1}^{P-1}\frac{P-1}{gcd(a,P-1)} \end{align} ans=1+a=1∑P−1b=1∑P−1[gcd(a,P−1)∣b]=1+a=1∑P−1k=1∑∞[k≤gcd(a,P−1)P−1]=1+a=1∑P−1gcd(a,P−1)P−1
设 f ( n ) = ∑ i = 1 n n g c d ( i , n ) f(n)=\sum_{i=1}^{n}\frac{n}{gcd(i,n)} f(n)=∑i=1ngcd(i,n)n
f ( n ) = ∑ i = 1 n n g c d ( i , n ) = ∑ i = 1 n ∑ d ∣ i , d ∣ n n d [ g c d ( i , n ) = d ] = ∑ d ∣ n n d ∑ i = 1 n d [ g c d ( i , n d ) = 1 ] = ∑ d ∣ n n d ϕ ( n d ) = ∑ d ∣ n d ϕ ( d ) \begin{align} f(n)&=\sum_{i=1}^{n}\frac{n}{gcd(i,n)}\\ &=\sum_{i=1}^{n}\sum_{d|i,d|n}\frac{n}{d}[gcd(i,n)=d]\\ &=\sum_{d|n}\frac{n}{d}\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]\\ &=\sum_{d|n}\frac{n}{d}\phi(\frac{n}{d})\\ &=\sum_{d|n}d\phi(d) \end{align} f(n)=i=1∑ngcd(i,n)n=i=1∑nd∣i,d∣n∑dn[gcd(i,n)=d]=d∣n∑dni=1∑dn[gcd(i,dn)=1]=d∣n∑dnϕ(dn)=d∣n∑dϕ(d)
因此要求的就是
a n s = 1 + f ( P − 1 ) = 1 + ∑ d ∣ ( P − 1 ) d ϕ ( d ) \begin{align} ans&=1+f(P-1)\\ &=1+\sum_{d|(P-1)}d\phi(d) \end{align} ans=1+f(P−1)=1+d∣(P−1)∑dϕ(d)
欧拉函数有两种公式可以求
- ϕ ( n ) = Π ( p i e i − p i ( e i − 1 ) ) ( p i ∣ n ) \phi(n)=\Pi (p_{i}^{e_{i}}-p_{i}^{(e_{i}-1)})(p_{i}|n) ϕ(n)=Π(piei−pi(ei−1))(pi∣n)
- ϕ ( n ) = n ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) … ( p i ∣ n ) \phi(n)=n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\dots(p_{i}|n) ϕ(n)=n(1−p11)(1−p21)…(pi∣n)
AC代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353;
LL phi(LL a) {LL res = a;for (LL i = 2; i * i <= a; i++) {if (a % i == 0) {res = res / i * (i - 1);while (a % i == 0) {a /= i;}}}if (a > 1) {res = res / a * (a - 1);}return res % mod;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);LL ans = 1;LL p;cin >> p;p--;LL i = 1;for (; i * i < p; i++) {if (p % i == 0) {ans = (ans + i % mod * phi(i) % mod) % mod;ans = (ans + (p / i) % mod * phi(p / i) % mod) % mod;}}if (i * i == p) {ans = (ans + i % mod * phi(i) % mod) % mod;}cout << ans << '\n';return 0;
}
