清北学堂 清北-Day1-R1-Count

题目描述

问有几个无序二元组 (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;
}
上一篇:hdu1116回溯N皇后问题


下一篇:吴恩达机器学习笔记58-协同过滤算法(Collaborative Filtering Algorithm)