给定一个正整数n,求1~n中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数n。
输出格式
共一行,包含一个整数,表示1~n中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例:
6
输出样例:
12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll primes[N],st[N],cnt,phi[N];
ll oo(ll n){
phi[1]=1;
for(ll i=2;i<=n;i++)
{
if(!st[i])primes[cnt++]=i,phi[i]=i-1;
for (ll j=0;primes[j]<=n/i;j++)
{
st[i*primes[j]]=1;
if(i%primes[j]==0)
{
phi[i*primes[j]]=phi[i]*primes[j]; //证法一,由欧拉函数的定义,在计算i的欧拉函数时,
//N后面的项已经被计算过了,i*primes[j]的欧拉函数较i
//的欧拉函数不过是N变为N*primes[j],即
//phi[i*primes[j]]=phi[i]*primes[j]
//证法二见图片;
break;
}
phi[i*primes[j]]=phi[i]*(primes[j]-1);
// 由他们得 积性关系(证明见链接)得 phi[i*primes[j]]=phi[i]*(primes[j]-1);
// 即 phi[i]*phi[primes[j]]
}
}
ll res=0;
for(ll i=1;i<=n;i++)res+=phi[i];
return res;
}
int main()
{
ll n;cin>>n;
cout<<oo(n)<<endl;
}
写的很好 ^_^
蟹蟹 ^_^