hdu 2824 The Euler function

柔光的暖阳◎ 2021-10-13 01:33 189阅读 0赞

### hdu 2824 The Euler function ###

*  题意
 *  源代码

# 题意 #

给定两个数a,b,求[a,b]区间欧拉函数的和
    ps：欧拉函数是求1~n与n互质的数，记为φ(n)，英文记为phi，特别的φ(1)=1;
    打表：首先计算出给定区间范围的欧拉函数值
    由于给定样例有多个，故用前缀和加快求解速度
    难点：快速求解区间范围欧拉函数
    根据欧拉函数的性质，可在线性范围内求解欧拉函数，同时可以筛选出素数
    1、phi(p)=p-1
    2、当p与i互质时有: phi(p*i)=phi(p)*phi(i)
    3、当i%p==0时有：phi(p*i)=p*phi(i)

# 源代码 #

#include<cstdio>
    using namespace std;
    const int  maxn= 3e6+3;
    typedef long long ll;
    bool visit[maxn];//标记是否为素数
    int prime[maxn/2];//保存素数 
    ll phi[maxn];//记录下标的欧拉函数 
    int tot;//记录素数的个数 
    void euler()
    { 
        phi[1]=1;
        for(int i=2;i<maxn;i++)
        { 
            if(!visit[i])//当i为素数时 
            { 
                prime[tot++]=i;
                phi[i]=i-1;//性质1
            }
            for(int j=0;j<tot;j++)
            { 
                int mid=i*prime[j];
                if(mid>maxn)break;
                visit[mid]=true;
                if(i%prime[j]==0)
                { 
                    phi[mid]=phi[i]*prime[j];//性质3 
                }
                else
                { 
                    phi[mid]=phi[i]*phi[prime[j]];//性质2 
                }
            }
        }
        for(int i=2;i<maxn;++i)phi[i]+=phi[i-1];
    }
    int main()
    { 
        euler();
        int a,b;
        while(~scanf("%d%d",&a,&b)){ 
            printf("%lld\n",phi[b]-phi[a-1]);
        }
    }