首先对一个数操作两次等于没有操作，所以每个数要么操作要么不操作。

首先$1$和所有质数显然一定要操作。

对于$x=p_1p_2$，之前已经被翻转过$3$次，所以一定要操作。

对于$x=p_1p_2p_3$，之前已经被翻转过$7$次，所以一定要操作。

…

对于$x = p_1p_2 …p_k$，之前已经被翻转过$2^k-1$次，所以一定要操作。

这样操作之后所有$x = p_1^{\alpha_1}p_2^{\alpha_2} …p_k^{\alpha_k}$都被翻转了$2^k$次，满足要求。

答案就是$\sum\limits _{i=1}^n \mu^2(i)$。

$\sum\limits_{i=1} ^ {n} \mu^2(i) = \sum\limits_{i=1} ^{\lfloor \sqrt n \rfloor} \mu(i) \lfloor \frac{n}{i^2} \rfloor$

杜教筛+整除分块即可。

时间复杂度不会算，反正过了。

#include <iostream>
#include <unordered_map>
#include <cmath>

using namespace std;

const int N = 20000010;

using i64 = long long;

int primes[N], cnt;
bool st[N];
int mu[N];
unordered_map<int, int> ans_mu;

void init(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
            int x = primes[j];
            st[i * x] = true;
            if (i % x == 0) {
                break;
            } else {
                mu[i * x] = -mu[i];
            }
        }
    }
    for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
}

int sum_mu(int n) {
    if (n <= 20000000) return mu[n];
    if (ans_mu.count(n)) return ans_mu[n];
    i64 res = 1;
    for (i64 l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res -= (r - l + 1) * sum_mu(n / l);
    }
    return ans_mu[n] = res;
}

int main() {
    init(20000000);
    i64 n;
    cin >> n;
    i64 res = 0;
    for (i64 l = 1, r; l <= n / l; l = r + 1) { 
        r = sqrt(n / (n / l / l));
        res += (sum_mu(r) - sum_mu(l - 1)) * (n / (l * l));
    }
    cout << res << '\n';
    return 0;
}