题目描述
问有几个无序二元组 (x; y) 满足 xy ≡ 1 (mod P ); 0 ≤ x < P; 0 ≤ y <P。无序二元组是指，如果 P = 10， (3; 7) 和 (7; 3) 只算一次。
输入
一行一个正整数 P。
输出
一行一个数，表示答案。
样例输入
10
样例输出
3
【样例输入 2】
8000000
【样例输出 2】
1600004
【数据范围与子任务】
Subtask1(20pts) $ P \le 10^3 $
Subtask2(30pts) $ P \le 10^5 $
Subtask3(50pts) $ P \le 10^7 $
本来以为是一道神仙数论题,结果是一道SB数论题
首先观察题目给出的式子: $ x \times y \equiv 1 \pmod p $
是不是感觉有一点似曾相识？
如果没有,那说明你逆元学得不太好(或者说没理解)
我们可以发现,这个式子正是在模 $ p $ 意义下 $ x $ 的逆元定义式
但是我们发现,这里的 $ p $ 不一定是一个质数,所以不能直接用逆元的方式来算
但是,我们知道逆元存在的条件的 $ x $ 与模数 $ p $ 互质,所以我们可以通过欧拉函数值 $ \phi (n) $ 来求出部分答案
欧拉函数: $ \phi (n) $ 表示小于等于 $ n $ 的数字中有多少个数字与 $ n $ 互质
欧拉函数可以通过线性筛筛出,代码如下:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
const int maxn=1e7+5;
int prime[maxn],phi[maxn];
int cnt=0,n,m;
bool vis[maxn];
void get_phi(int n){
phi[1]=1;vis[1]=1;
for(int i=2;i<n;++i){
if(!vis[i]){
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
vis[i*prime[j]]=true;
if(!(i%prime[j])){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main(){
scanf("%d%d",&n,&m);
get_phi(n+5);
while(m--){
register int x;
scanf("%d",&x);
puts(vis[x]?"No":"Yes");
}
return 0;
}
也可以使用单个欧拉函数值的求法,复杂度是 $ \Theta \sqrt{n} $
在这个题目中显然后一种比较优秀,这里也同样给出代码:
inline int Euler(int n){
register int res=n,a=n;
for(int 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;
}
千万不要以为这时候这道题就做完了,其实我们还需要考虑一种情况:
当 $ x = y $ 的时候,也即是 $ x^2 \equiv 1 \pmod p $
这种情况也是满足的,所以也要把这种情况统计上,这样这道题才算是AC了
AC代码:
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define ll long long
int mod,ans;
inline int Euler(int n){
register int res=n,a=n;
for(int 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;
}
int main(){
scanf("%d",&mod);
ans+=Euler(mod);
for(ll i=1;i<=mod;++i) if(i*i%mod==1) ++ans;
printf("%d\n",(ans>>1));
return 0;
}