hdu3572线性欧拉筛

用线性筛来筛，复杂度O(n)

#include<bits/stdc++.h>
#include<ext/rope>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;
using namespace __gnu_cxx;

const double g=10.0,eps=1e-7;
const int N=3000000+10,maxn=100000+10,inf=0x3f3f3f;

bool isprime[N];
int prime[N],cnt,phi[N];
void getprime()
{
    cnt=0;
  //  memset(isprime,1,sizeof isprime);
  //  isprime[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!isprime[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<N;j++)
        {
            isprime[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}
int main()
{
    getprime();
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        ll ans=0;
        for(int i=a;i<=b;i++)
            ans+=phi[i];
        printf("%I64d
",ans);
    }
    return 0;
}
/*******************

********************/

View Code

类似于素数筛，利用欧拉函数是积性函数f(a*b)=f(a)*f(b)性质

素数i的欧拉函数值为i-1，如果是合数，那么利用最小的因子来筛它