bzoj 5455

莫比乌斯反演

答案求$sum_{i=1}^{n}{sigma(i^{2})}$

转化一下

设$f(i)=sum_{d|i}{mu(d)^{2}}$

答案等于

$sum_{i=1}^{n}sum_{d|i}{f(d)}$

为什么呢，这么思考一下，我们求的是每个$i^{2}$的约数个数，枚举$i$的约数$d$,$d^{2}$是$i^{2}$的约数

假设对$i^{2}$进行质因数分解后，设质数$p$是$i$的约数，指数是$a$，那么在$i^2$的约数中$p$的次数可以是$[0,2a]$

这时我们枚举$i$的约数$d$，对于质数$p$，在$d$中的次数为$b$,在$d^{2}$中的次数为$2b$,通过枚举$d$我们可以枚举到所有$2b leq 2a$

但是没有枚举到奇数次指数，这时枚举$d$的约数$D$，求$f(D)$的和，相当于枚举给所有$2b$是否$-1$，这样就覆盖到了所有奇数偶数情况。

继续化简

$ans=sum_{i=1}^{n}sum_{d|i}sum_{D|d}{mu(D)^{2}}$

把$D$提到最外层

$ans=sum_{D=1}^{n}{mu(D)^{2}S([frac{n}{D}])}$

$S(n)=sum_{i=1}^{n}{[frac{n}{i}]}$

可以$O(sqrt{n})$时间求出来

考虑前一项

$sum_{i=1}^{n}{mu(i)^{2}}=sum_{i=1}^{sqrt{n}}{mu(i)[frac{n}{i^{2}}]}$

也可以$O(sqrt{n})$求出来

总复杂度$O(n^{frac{2}{3}})$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int n;
int mu[maxn], p[maxn], mark[maxn];
ll f(int n) {
    ll ret = 0;
    for(int i = 1; i * i <= n; ++i) ret += 1LL * mu[i] * (n / (1LL * i * i));
    return ret;
}
void init() {
    mu[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        if(!mark[i]) {
            p[++p[0]] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= p[0] && i * p[j] < maxn; ++j) {
            mark[i * p[j]] = 1;
            if(i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
}
ll g(int n) {
    ll ret = 0;
    for(int i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        ret += 1LL * (j - i + 1) * (n / i);
    }
    return ret;
}
int main() {
    init();
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ll ans = 0, now = 0, pre = 0;
        for(int i = 1, j; i <= n; i = j + 1) {
            j = n / (n / i);
            now = f(j);
            ans += 1LL * g(n / i) * (now - pre);
            pre = now;
        }
        printf("%lld
", ans);
    }
    return 0;
}