51nod 1239 欧拉函数之和(杜教筛)

Description:

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

Sample Input:

5

Sample Output:

10

题目链接

此题为求出区间 $[1,n]$[1,n] 之间的欧拉函数之和即欧拉函数前缀和，而欧拉函数 $\phi$φ 我们已知为积性函数

求积性函数的前缀和那么显然需要利用到杜教筛

杜教筛的学习可以参考

唐老师(skywalkert)的博客 浅谈一类积性函数的前缀和

吉老师(jiry_2)的博客 论逗逼的自我修养之寒假颓废记

任之洲的论文 积性函数求和的几种方法 (2016 年信息学奥林匹克中国国家队候选队员论文集)

杜教筛用于在低于线性的时间复杂度内求出一些积性函数的前缀和

现在我们需要求出积性函数 $\phi$φ 的前缀和，考虑到欧拉函数的性质 $\phi \ast I=id$φ∗I=id （ $\ast$∗ 为狄利克雷卷积 ）

根据杜教筛的核心式就有
$\sum _{i=1}^n\phi \left(i\right)=\sum _{i=1}^n\left(\phi \right(i)\ast I(i\left)\right)-\sum _{i=2}^{n}I\left(i\right)\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\phi \left(j\right)=\sum _{i=1}^{n}id\left(i\right)-\sum _{i=2}^{n}I\left(i\right)\sum _{j=1}^{\lfloor \frac{n}{i}\rfloor }\phi \left(j\right)$i=1∑n​φ(i)=i=1∑n​(φ(i)∗I(i))−i=2∑n​I(i)j=1∑⌊in​⌋​φ(j)=i=1∑n​id(i)−i=2∑n​I(i)j=1∑⌊in​⌋​φ(j)
显然其中 $I$I​ 与 $id$id​ 的前缀和很好求，再用整除分块和记忆化搜索优化一下就可以了

AC代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 5e6 + 5;
const ll mod = 1e9 + 7;
const ll inv = 5e8 + 4;

bool IsPrime[maxn];
int Tot;
ll Prime[maxn];
int Phi[maxn];
ll PrefixPhi[maxn];

void Sieve() {
    for (int i = 2; i < maxn; ++i) IsPrime[i] = true;
    Phi[1] = 1;
    for (ll i = 2; i < maxn; ++i) {
        if (IsPrime[i]) {
            Phi[i] = i - 1;
            Prime[Tot++] = i;
        }
        for (ll j = 0; j < Tot && i * Prime[j] < maxn; ++j) {
            IsPrime[i * Prime[j]] = false;
            if (i % Prime[j] == 0) {
                Phi[i * Prime[j]] = Phi[i] * Prime[j];
                break;
            }
            Phi[i * Prime[j]] = Phi[i] * Phi[Prime[j]];
        }
    }
    for (int i = 1; i < maxn; ++i) PrefixPhi[i] = (PrefixPhi[i - 1] + Phi[i]) % mod;
}

map<ll, ll> SumPhi;

ll SigmaPhi(ll Key) {
    if (Key < maxn) return PrefixPhi[Key];
    if (SumPhi[Key]) return SumPhi[Key];
    ll Ans = Key % mod * (Key % mod + 1) % mod * inv % mod;
    for (ll l = 2, tp; l <= Key; l = tp + 1) {
        tp = Key / (Key / l);
        Ans = (Ans - (tp - l + 1) % mod * SigmaPhi(Key / l) % mod + mod) % mod;
    }
    SumPhi[Key] = Ans;
    return SumPhi[Key];
}

ll N;

int main(int argc, char *argv[]) {
    Sieve();
    scanf("%lld", &N);
    printf("%lld\n", SigmaPhi(N));
    return 0;
}