51nod 1239 欧拉函数之和

描述

对正整数 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的结果。

Input

输入一个数N。(2 <= N <= 10^10)

Output

输出S(n) Mod 1000000007的结果。

Input示例

Output示例

思路

和 51nod 1244 莫比乌斯函数之和十分类似的一道题，因此我们可以采用同样的方法推出公式。

求 $\sum_{i=1}^{n}\varphi(i)$

我们设 $M(n)=\sum_{i=1}^{n}\varphi(i)$

已知 $\sum_{d|n}\varphi(d)=n$

所以有 $\sum_{i=1}^{n}\sum_{d|i}\varphi(d)=\sum_{i=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}\varphi(d)=\sum_{i=1}^{n}M(\lfloor\frac{n}{i}\rfloor)=\frac{n×(n+1)}{2}$

因为 $\sum_{i=1}^{n}M(\lfloor\frac{n}{i}\rfloor)=M(n)+\sum_{i=2}^{n}M(\lfloor\frac{n}{i}\rfloor)=\frac{n×(n+1)}{2}$

所以 $M(n)=\frac{n×(n+1)}{2}-\sum_{i=2}^{n}M(\lfloor\frac{n}{i}\rfloor)$

同样我们可以通过记忆化搜索以及分块来优化时间。

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;
}