本文共 1308 字，大约阅读时间需要 4 分钟。

Problem Description

The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+….+ (b)

Input

There are several test cases. Each line has two integers a, b (2< a< b<3000000).

Output

Output the result of (a)+ (a+1)+….+ (b)

Sample Input

3 100

Sample Output

3042

题目大意：求a…b的欧拉函数和

详情参见 注意：要用long long.

#include
   
    #include
    
     using namespace std;const int maxn=3000000;int m[maxn+1],pri[maxn+1],phi[maxn+1];long long ans;void euler(){    int cnt=0;    phi[1]=1;    for(int i=2;i<=maxn;i++)    {        if(!m[i])        {            pri[++cnt]=m[i]=i;            phi[i]=i-1;        }        for(int j=1;j<=cnt&&pri[j]*i<=maxn;j++)        {            m[i*pri[j]]=pri[j];            if(m[i]==pri[j])            {                phi[i*pri[j]]=phi[i]*pri[j];                break;            }            else                 phi[i*pri[j]]=phi[i]*phi[pri[j]];        }    }}int main(){    euler();    int a,b;    while(scanf("%d%d",&a,&b)==2)    {        ans=0;        for(int i=a;i<=b;i++)            ans+=phi[i];        printf("%lld\n",ans);    }    return 0;}
    
   

转载地址：https://blog.csdn.net/Rlt1296/article/details/51882800 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！