题目描述
题目要求:给定一个数n,求出1——n中每个数的欧拉函数之和。
按道理是可以直接用欧拉公式一次计算的,但是这样的实践复杂度比较大。求1到n中所有的欧拉函数之和,是不是和求1-n种所有的质数个数的问题比较相似呢?这启发我们探寻是否可以使用线性筛法利用欧拉公式形式的特殊性进行优化。
三种情况:
1.当前数本身就是质数:这意味着1——n-1中的所有数都是与n互质的,即eular[n]=n-1;
2.当前数可以整除i,写出欧拉公式的形式可以发现eular[primes[j]乘以i]=eular[i]乘以primes[j];
3.当前数不可以整除i,写出欧拉公式的形式可以发现eular[primes[j]乘以i]=eular[i]乘以(primes[j]-1);
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
const int N =1000010;
int primes[N],cnt;
int euler[N];
bool st[N];
void get_eulur(int n)
{
euler[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
euler[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
euler[primes[j]*i]=euler[i]*primes[j];
break;
}
euler[primes[j]*i]=euler[i]*(primes[j]-1);
}
}
}
int main()
{
int n;
cin>>n;
get_eulur(n);
LL res=0;
for(int i=1;i<=n;i++) res+=euler[i];
printf("%lld",res);
return 0;
}