题目描述
给定一个正整数 n,求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
样例
输入样例:
6
输出样例:
12
算法1
(线性筛欧拉函数)
用循环一个个求欧拉函数的话模板复杂度会到n*sqrt(n),很大,所以将线性筛和欧拉函数结合起来
分三个情况一次循环求出1~n的欧拉函数
关于欧拉函数定义可见 https://www.acwing.com/file_system/file/content/whole/index/content/3955510/
自有点丑,见谅q(≧▽≦q)
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int phi[N],primes[N],cnt;
bool st[N];
int n;
ll get_enler(int n)
{
phi[1]=1;//1需要特判
ll res=0;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
phi[i]=i-1;//情况1
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)
{
phi[i*primes[j]]=phi[i]*primes[j];//情况2
break;
}
phi[i*primes[j]]=phi[i]*(primes[j]-1);//情况3
}
}
for(auto i:phi)res+=i;//算求和
return res;//返回
}
int main()
{
cin>>n;
cout<<get_enler(n)<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla