Editorial for Product Divisible by Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

#include <bits/stdc++.h>

using namespace std;

int main() {
    // Her 1 <= x <= n için x^2lerin x'ten büyük bölen sayıları toplamı
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n = 5e6; cin >> n;
    vector<bool> p(n + 1, true);
    vector<int> p_div(n + 1);
    long long ans = 0;
    p[0] = p[1] = false;
    for (int i = 1; i <= n; i++) {
        if (p[i]) {
            p_div[i] = i;
            if (i <= n/i) for (int j = i * i; j <= n; j += i) p[j] = false, p_div[j] = i;
        }
        int cnt = 1;
        int x = i;
        while (x > 1) {
            int cur = p_div[x];
            int exp = 0;
            for (; x % cur == 0; x /= cur, exp++);
            cnt *= 2 * exp + 1;
        }
        ans += cnt / 2;
    }
    cout << ans << "\n";
}