本文共 2024 字，大约阅读时间需要 6 分钟。
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要求a到b的欧拉函数对应的值的和
直接上模板
#include#include #include #include typedef long long ll;using namespace std;const int size=3000000;ll euler[size];void init(){ memset(euler,0,sizeof(euler)); euler[1]=1; for(ll i=2;i<=size;i++) { if(euler[i]==0) { for(ll j=i;j<=size;j+=i) { if(euler[j]==0) { euler[j]=j; } euler[j]=euler[j]/i*(i-1); } } }}int main(){ init(); ios::sync_with_stdio(false); ll a,b; while(cin>>a>>b) { ll sum=0; for(ll i=a;i<=b;i++) sum+=euler[i]; cout< <
后看到网上有人用前缀和做：
#include#include #include #include #define ll long longusing namespace std;const int size=3000000;ll euler[size+10];void init(){ memset(euler,0,sizeof(euler)); euler[1]=1; for(ll i=2;i<=size;i++) { if(euler[i]==0) { for(ll j=i;j<=size;j+=i) { if(euler[j]==0) { euler[j]=j; } euler[j]=euler[j]/i*(i-1); //先进行除法是为了防止中间数据的溢出 } } } for(ll i=3;i<=size;i++) //前缀和 { euler[i]+=euler[i-1]; }}int main(){ init(); //初始化，首先求出每个数对应的质因数个数 ll a,b; while(~scanf("%lld%lld",&a,&b)) { printf("%lld\n",euler[b]-euler[a-1]); } return 0;}
转载地址：http://epyzi.baihongyu.com/