noi.ac180 divisors

$$ \sum_{1\le i\le n}{\sum_{d|i}{gcd\left( d,\frac{i}{d} \right)}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le n}{\sum_{d|i}{\left[ gcd\left( d,\frac{i}{d} \right) =x \right]}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le \lfloor \frac{n}{x^2} \rfloor}{\sum_{d|i}{\left[ gcd\left( d,\frac{i}{d} \right) =1 \right]}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le i\le \lfloor \frac{n}{x^2} \rfloor}{\sum_{d|i}{\sum_{k|d,k|\frac{i}{d}}{\mu \left( k \right)}}}} \\ =\sum_{1\le x\le n}{x\sum_{1\le k\le \lfloor \frac{n}{x^2} \rfloor}{\mu \left( k \right)}\sum_{1\le i\le \lfloor \frac{n}{k^2x^2} \rfloor}{\sum_{d|i}{1}}} \\ \text{设}f\left( x \right) =\sum_{1\le i\le x}{\sum_{d|i}{1}}=\sum_{1\le i\le x}{\lfloor \frac{x}{i} \rfloor} \\ \text{则有}\sum_{1\le x\le n}{x\sum_{1\le k\le \lfloor \frac{n}{x^2} \rfloor}{\mu \left( k \right) f\left( \lfloor \frac{n}{k^2x^2} \rfloor \right)}} \\ \text{令}T=kx,\text{则有} \\ \sum_{\,\,1\le T\le n}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \sum_{k|T}{\mu \left( k \right) \frac{T}{k}}}=\sum_{1\le T\le n}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \varphi \left( T \right)} \\ \text{由于}T^2\le n,\text{故}T\le \sqrt{n} \\ \text{则有}\sum_{1\le T\le \sqrt{n}}{f\left( \lfloor \frac{n}{T^2} \rfloor \right) \varphi \left( T \right)} \\ \text{复杂度}O\left( \sum_{1\le i\le \sqrt{n}}{\sqrt{\frac{n}{i^2}}} \right) =O\left( \sqrt{n}\log n \right) \\ \\ $$

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 5e6;
bool isPrime[LARGE + 1];
std::vector<int_t> primes;
int_t factor[LARGE + 1], phi[LARGE + 1];
int_t f(int_t n) {
    int_t i = 1, result = 0;
    // int_t px = n;
    while (i * i <= n) {
        result += (n / i);
        // px--;
        i++;
    }
    int_t k = n / i;
    while (i <= n) {
        // int_t t
        int_t next = n / k;
        result += k * (next - i + 1);
        i = next + 1;
        k--;
    }
    return result;
}
int main() {
    int_t n;
    cin >> n;
    int_t sqrt = ::sqrt(n) + 1;
    memset(isPrime, 1, sizeof(isPrime));
    phi[1] = 1;
    for (int_t i = 2; i <= sqrt; i++) {
        if (isPrime[i]) {
            factor[i] = i;
            primes.push_back(i);
        }
        for (int_t x : primes) {
            if (i * x > sqrt) break;
            isPrime[i * x] = false;
            factor[i * x] = x;
            // factor[i * x] = x;
            if (i % x == 0) break;
        }
    }
#ifdef DEBUG
    for (int_t x : primes) cout << x << endl;
#endif
    phi[1] = 1;
    for (int_t i = 2; i <= sqrt; i++) {
        int_t p = factor[i];
        if (i / p % p == 0)
            phi[i] = phi[i / p] * p;
        else
            phi[i] = phi[i / p] * (p - 1);
    }
    int_t result = 0;
    for (int_t i = 1; i * i <= n; i++) {
        result += f(n / (i * i)) * phi[i];
#ifdef DEBUG

        cout << "phi " << i << " = " << phi[i] << endl;

#endif
    }
    cout << result << endl;
    return 0;
}