bzoj 4176 Lucas的数论

Description

去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。

在整理以前的试题时，发现了这样一道题目“求Sigma(f(i)),其中1<=i<=N”，其中 表示i的约数个数。他现在长大了，题目也变难了。
求如下表达式的值：

其中 表示ij的约数个数。
他发现答案有点大，只需要输出模1000000007的值。

Input

第一行一个整数n。

Output

一行一个整数ans，表示答案模1000000007的值。

Sample Input

2

Sample Output

8

HINT

对于100%的数据n <= 10^9。

题解

具体见总结

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = 5000000, mod = 1000000007;
bool p[N + 10];
int n, T, pr[N + 10];
long long mu[N + 10];
map<int, long long> mmu;
void init() {
    mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!p[i])
            pr[++pr[0]] = i, mu[i] = -1;
        for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) {
            p[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                mu[i * pr[j]] = 0;
                break;
            }
            mu[i * pr[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}
long long mus(int n) {
    if (n <= N) return mu[n];
    if (mmu.count(n)) return mmu[n];
    long long tmp = 1;
    for (int i = 2, las; i <= n; i = las + 1) {
        las = n / (n / i);
        (tmp -= 1ll * mus(n / i) * (las - i + 1)) %= mod;
        if (las == n) break;
    }
    return mmu[n] = tmp % mod;
}
long long f(int n) {
    long long ans = 0;
    for (int i = 1, las; i <= n; i = las + 1) {
        las = n / (n / i);
        (ans += 1ll * (n / i) * (las - i + 1)) %= mod;
        if (las == n) break;
    }
    return (ans * ans) % mod;
}
main() {
    init();
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 1, las; i <= n; i = las + 1) {
        las = n / (n / i);
        (ans += 1ll * (mus(las) - mus(i - 1)) * f(n / i)) %= mod;
        if (las == n) break;
    }
    printf("%lld\n", (ans + mod) % mod);
}