线性筛欧拉函数

　　　这个算法是在线性时间内在筛素数的同时求出所有数的欧拉函数(对于正整数n,小于等于n的数中与n互质的数的数目。

先明确几个性质（p为质数）：

　　1*　　φ（p）=p-1。（显然，【1，p-1】内的任意整数都与p互质）。

　　2*　　若t mod p==0那么φ（i*p）=p*φ(i)

　　　　　若t 和 u 互质，那么φ(t*u)=φ(t)*φ(u).

　　3*　　φ(p^a)=(p-1)*p^(a-1)　　即p^a-p^a-1.

　　　　　　　　　　　　　　　　　因为p的倍数和p^a 一定不互质，所以有 p^a /p 个数与p^a不互质。

　　4*　　φ(n)=n*(1-1/p1)*(1-1/p2).....*(1-1/pm) 这算是对3*的一个推广

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
#define N 10000009
#define LL long long 
LL prime[N/10],cnt,n,ans,tot;
LL phi[N];//欧拉函数的值
bool mark[N] ;
void first()
{
    phi[1]=1;
    for(LL i=2;i<=n;i++)
    {
        ans+=tot;
        if(!mark[i])    
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        
        for(LL j=1;j<=cnt;j++)
        {
            if(i*prime[j]>n)    break;
            mark[i*prime[j]]=1;            
            if(i%prime[j] ==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    return ;
}
int main()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    scanf("%lld",&n);
    first();    
    for(int i=1;i<=n;i++)
        ans+=phi[i];
    cout<<ans;
    return 0;
}

线性筛欧拉函数

相关推荐