azLBDq - Online C++0x Compiler & Debugging Tool

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAX = 1e5;
const int LIM = MAX + 15;

vector<int> prime; // tập các số nguyên tố từ 2 tới lim
vector<int> lpf; // lowest_prime_factor[x] trả về ước nguyên tố nhỏ nhất của x
vector<bool> is_prime;
int sieve(int lim = MAX)
{
    if (lim <= 1) {
        return 0;
    }
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);
    is_prime.assign(lim + 1, true);

    lpf[1] = 1;
    for (int i = 3; i <= lim; i += 2) {
        if (is_prime[i]) {
            prime.push_back(lpf[i] = i);
        }
        for (int j = 0; j < prime.size() && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j) {
            lpf[prime[j] * i] = prime[j];
            is_prime[prime[j] * i] = false;
        }
    }
    return prime.size();
}

int Mask(int x)
{
    int mask = 1;
    while (x > 1)
    {
        int p = lpf[x], f = 0; // p^f
        do x /= p, ++f; while (p == lpf[x]);
        const int r = f % 2;
        if (r == 1) {
            mask *= p;
        }
    }
    return mask;
}

int cnt[LIM];
long long solve(int n)
{
    memset(cnt, 0, sizeof(cnt[0]) * (n + 1));
    sieve(n);

    long long res = 0;
    for (int x = 1; x <= n; ++x) {
        res += cnt[Mask(x)];    // Ghép U với tất cả Y = V * Q^2 có Mask(X) = Mask(Y)
        ++cnt[Mask(x)];         // Tìm được thêm một giá trị X = U * P^2 với U = Mask(X)
    }

    return res;
}

int main()
{
    for (int n = 1; n <= 100; ++n) {
        cout << solve(n) << " ";
    }
    cout << endl;
    return 0;

    for (int n; cin >> n; ) {
        cout << solve(n) << endl;
    }
    return 0;
}