性质:
欧拉函数用希腊字母φ表示,φ(N)表示N的欧拉函数.
对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数.
欧拉函数的一些性质:
1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.
2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*…*Pn^qn.
φ(N)=N*(1-1/P1)(1-1/P2)…*(1-1/Pn).
3.除了N=2,φ(N)都是偶数.
4.设N为正整数,∑φ(d)=N (d|N).
根据性质2,我们可以在O(sqrt(n))的时间内求出一个数的欧拉函数值.
#include<cstdio>
#define ll long long
#define maxn 100000
unsigned int prime[],l,ans[],pre[],n;
bool flag[];
void Eorue()
{
for(int i=;i<=maxn;i++)
{
if(!flag[i]){
prime[l++] = i;
pre[i] = i-;
++ans[i];
}
for(int j=;j<l&&prime[j]*i<=maxn;j++)
{
flag[prime[j]*i] = true;
if(i%prime[j]==){
pre[i*prime[j]] = pre[i]*prime[j];
break;
}
pre[i*prime[j]] = pre[i]*(prime[j]-);
}
}
}
void gao()
{
for(int i=;i<=maxn;i++)
for(int j=;j<l&&prime[j]*i<=maxn;j++)
ans[prime[j]*i] += pre[i]*2;
for(int i=;i<=maxn;i++)
ans[i]+=ans[i-];
}
int main()
{
Eorue();
gao();
while(scanf("%u",&n)!=EOF)
printf("%u\n",ans[n]);
return ;
}
2.0 顺便求每个数的质因子和质数信息
#include<cstdio>
#include<algorithm>
#include<iostream>
#define maxn 100001
#define LL long long
using namespace std;
// 欧拉函数3
LL eular[maxn];
int prime[maxn][],num[maxn],flag[maxn],AM = ;
void Eorue(){
eular[] = ;
for(int i = ;i < maxn; i++){
if(eular[i] == i){
flag[AM++] = i;
eular[i] = i - ;
prime[i][num[i]++] = i;
for(int j = ; j * i < maxn; j++){
eular[i * j] = eular[i * j] * (i - ) / i;
prime[i * j][num[i * j]++] = i;
}
}
eular[i] += eular[i-];
}
}
求单个的欧拉函数
LL get_eular(LL n){
LL ret=1;
for(int i=2;i*i<=n;i++)
if(n%i==0){
ret*=i-1;
n/=i;
while(n%i==0){
n/=i;
ret*=i;
}
}
if(n>1)
ret*=n-1;
return ret;
}