描述
对正整数 n ，欧拉函数是小于或等于 n 的数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 Euler’s totient function 、 φ 函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为 1,3,5,7 均和 8 互质。
S(n) = Phi(1) + Phi(2) + …… Phi(n)，给出n，求S(n)，例如：n = 5，S(n) = 1 + 1 + 2 + 2 + 4 = 10，定义Phi(1) = 1。由于结果很大，输出Mod 1000000007的结果。
输入一个数N。(2 <= N <= 10^10)
Output
输出S(n) Mod 1000000007的结果。
5
Output示例
10
思路
和 51nod 1244 莫比乌斯函数之和 十分类似的一道题，因此我们可以采用同样的方法推出公式。
求
∑ni=1φ(i)
我们设
M(n)=∑ni=1φ(i)
已知
∑d|nφ(d)=n
所以有
∑ni=1∑d|iφ(d)=∑ni=1∑⌊ni⌋d=1φ(d)=∑ni=1M(⌊ni⌋)=n×(n+1)2
因为
∑ni=1M(⌊ni⌋)=M(n)+∑ni=2M(⌊ni⌋)=n×(n+1)2
所以
M(n)=n×(n+1)2−∑ni=2M(⌊ni⌋)
同样我们可以通过记忆化搜索以及分块来优化时间。
AC 代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef __int64 LL;
const int maxn =
5000000;
const int MOD =
1000000007;
const int mod =
1e5+
7;
map<LL,LL> mp[mod];
LL mu[maxn];
int phi[maxn];
void init()
{
int j;
phi[
1] =
1;
for(
int i =
2; i < maxn; i++)
if(!phi[i])
for(j = i; j < maxn; j+=i)
{
if(!phi[j])phi[j] = j;
phi[j] = phi[j] / i * (i-
1);
}
for(
int i=
1; i<maxn; i++)
mu[i]=(mu[i-
1]+phi[i])%MOD;
}
LL call(LL x)
{
if(x<maxn)
return mu[x];
LL p=mp[x%mod][x];
if(p)
return p;
LL ans=(((x%MOD)*((x+
1)%MOD)%MOD)*
500000004)%MOD;
for(LL i=
2,la=
0; i<=x; i=la+
1)
{
la=x/(x/i);
ans=(ans-(la-i+
1)%MOD*call(x/i)%MOD+MOD)%MOD;
}
mp[x%mod][x]=ans;
return ans;
}
int main()
{
ios::sync_with_stdio(
false);
init();
LL n;
while(
cin>>n)
cout<<call(n)<<endl;
return 0;
}
