[2016 CCPC Hangzhou j] just a math problem (Mobius inversion)

The question

$T$ Group input , Give a positive integer at a time $n$, Definition $f(k)$ by $k$ The number of quality factors ,$g(k)=2^{f(i)}$, seek
$$\sum _{i=1}^{n}g(i)$$
$1\le T\le 50,1\le n\le 10^{12}$

analysis ：

First $2^{f(i)}$ It's not easy to calculate directly , Consider the meaning of combination , Find out $2^{f(i)}$ It's from $i$ The number of schemes that select several subsets from all the prime factors of , hypothesis $i=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$, So we can enumerate $i$ All divisors of $d$, Bring the divisor into the Mobius function , Then remove all existence greater than or equal to $2$ Inferior prime factor , So each ${\alpha }_i$ Can only take $0$ or $1$, But if there are an odd number of prime factors, the value of Mobius function is negative , So square it , namely

$$\sum _{i=1}^n{2}^{f(i)}=\sum _{i=1}^n\sum _{d\mid i}{\mu }^2(d)$$

Exchange summation order

$$\sum _{d=1}^n{\mu }^2(d)\lfloor \frac{n}{d}\rfloor$$
At this point, you can apply Complete square The formula of this problem
$$\sum _{i=1}^n{\mu }^2(i)=\sum _{i=1}^n\sum _{d^2\mid i}\mu (d)$$
Substituting to obtain
$$\sum _{i=1}^n\lfloor \frac{n}{i}\rfloor \sum _{d^2\mid i}\mu (d)$$
Exchange summation order
$$\sum _{d=1}^{\sqrt{n}}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d^2}\rfloor }\lfloor \frac{n}{i\times d^2}\rfloor =\sum _{d=1}^{\sqrt{n}}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d^2}\rfloor }\lfloor \frac{\lfloor \frac{n}{d^2}\rfloor }{i}\rfloor$$
The latter formula can be divided into blocks directly , Pay attention to optimization when Mobius function is not $0$ Only then calculates the answer , And remember the answers in blocks , Complexity is more metaphysical , This question is for $15$ second .

Code ：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int cnt;
vector<int> primes(1e6 + 1), mobius(1e6 + 1), block(1e6 + 1);
vector<bool> st(1e6 + 1);
void init(int n) {
    
    mobius[1] = 1;
    for (int i = 2; i <= n; i ++) {
    
        if (!st[i]) {
    
            primes[cnt ++] = i;
            mobius[i] = -1;
        }
        for (int j = 0; i * primes[j] <= n; j ++) {
    
            int t = i * primes[j];
            st[t] = 1;
            if (i % primes[j] == 0) {
    
                mobius[t] = 0;
                break;
            }
            mobius[t] = -mobius[i];
        }
    }
};
void solve() {
    
    int n;
    cin >> n;
    int res = 0;
    auto sum = [&](int n) {
    
        if (n < 1e6 && block[n]) {
    
            return block[n];
        }
        int res = 0;
        for (int l = 1, r; l <= n; l = r + 1) {
    
            r = n / (n / l);
            res = (res + (n / l) * (r - l + 1) % mod) % mod;
        }
        if (n > 1e6) {
    
            return res;
        } else {
    
            return block[n] = res;
        }
    };
    for (int i = 1; i * i <= n; i ++) {
    
        if (mobius[i]) {
    
            res = (res + mobius[i] * sum(n / (i * i)) % mod + mod) % mod;
        }
    }
    cout << res << "\n";
}
signed main() {
    
    init(1e6);
    cin.tie(0) -> sync_with_stdio(0);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t ++) {
    
        cout << "Case #" << t << ": ";
        solve();
    }
}