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<cstdio>#include<algorithm>#include<iostream>#include<cstring>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<<sum<<endl; } return 0;}
后看到网上有人用前缀和做:
#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#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;}
联系客服