欧拉函数
(1)~(n)中与(n)互质的数的个数被称为欧拉函数，记为(varphi(n))
[varphi(n)=n*frac{p_{1}-1}{p_{1}} * frac{p_{2}-1}{p_{2}} * ... * frac{p_{m}-1}{p_{m}}=n*prod_{质数p|n}^{} (1-frac{1}{p})
]
根据欧拉函数的计算式，在分解质因数的时候求出欧拉函数即可：
int phi_(int n){
int res=n;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
res=res/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}
题解
题目
自己推一下很容易发现，一个点((x,y))能被看到，当且仅当(gcd(x,y)=1)
又因为这是一个方阵，能看到的点关于((1,1))到((n,n))的对角线是对称的，所以求出一半的点的数量(ans)（不包括((1,1))），(ans imes2+1)即为最终结果
- 为什么加和的时候是(1)~((n-1))?
因为点((1,1))是不包括的，三角形只有((n-1))排 - 为什么要特判(n==1)?
因为只有一个点((1,1))的时候就是他看到的就是0个啊
code
纯欧拉函数
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#define maxn 40010
using namespace std;
template<typename T>
inline void read(T &x){
x=0; bool flag=0; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n;
int ans,phi[maxn];
int phi_(int n){
int res=n;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
res=res/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}
int main(){
read(n);
if(n==1){cout<<0<<endl; return 0;}
for(int i=1;i<=n;i++) phi[i]=phi_(i);
for(int i=1;i<=n-1;i++) ans+=phi[i];
cout<<2*ans+1<<endl;
return 0;
}
Eratosthenes筛法
(O(n log n))
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#define maxn 40010
using namespace std;
template<typename T>
inline void read(T &x){
x=0; bool flag=0; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n;
int ans,phi[maxn];
void phi_(int n){
for(int i=1;i<=n;i++) phi[i]=i;
for(int i=2;i<=n;i++){
if(phi[i]==i){
for(int j=i;j<=n;j+=i){
phi[j]=phi[j]/i*(i-1);
}
}
}
}
int main(){
read(n);
if(n==1){cout<<0<<endl; return 0;}
phi_(n);
for(int i=1;i<=n-1;i++) ans+=phi[i];
cout<<2*ans+1<<endl;
return 0;
}
//Eratosthenes筛法，O(n log n)
线性筛
(O(n))
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define maxn 40010
using namespace std;
template<typename T>
inline void read(T &x){
x=0; bool flag=0; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
for(;isdigit(c);c=getchar()) x=x*10+(c^48);
if(flag) x=-x;
}
int n;
int ans,cnt,mindiv[maxn],isprime[maxn],phi[maxn];
void phi_(int n){
cnt=0;//质数数量
memset(mindiv,0,sizeof(mindiv));//最小质因子
phi[1]=1;
for(int i=2;i<=n;i++){
if(mindiv[i]==0){//i是质数
mindiv[i]=i;
isprime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;(j<=cnt)&&(i*isprime[j]<=n);j++){
mindiv[i*isprime[j]]=isprime[j];
phi[i*isprime[j]]=phi[i]*(i%isprime[j]?isprime[j]-1:isprime[j]);//"isprime[j]-1" and "phi[isprime[j]]" both right
if(mindiv[i]==isprime[j]) break;
}
}
}
int main(){
read(n);
if(n==1){cout<<0<<endl; return 0;}
phi_(n);
for(int i=1;i<=n-1;i++) ans+=phi[i];
cout<<2*ans+1<<endl;
return 0;
}
//线性筛，O(n)