백준 17425번

17425(3).cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MAX = 1e6;

struct node{
    ll div=1, f=0, g=0;
};
vector<node> v;

void func(ll x, ll b) { // x = a*b
    ll a = x/b;

    if (b == 1) { // if x is prime
        v[x] = {1, 1+x, 0};
    }
    else { // if x is not prime
        int num = 0;
        int val = x;
        while (val%b == 0) {
            val /= b;
            num ++;
        }
        v[x].f = v[a].f + pow(b,num)*v[val].f;
    }

    v[x].g = v[x-1].g + v[x].f;
}

int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    v.resize(1e6+1);

    for (ll i=2; i*i<=MAX; i++) {
        if (v[i].div > 1) continue;
        for (ll j=2; i*j<=MAX; j++) {
            v[i*j].div = i;
        }
    }

    v[1] = {1, 1, 1}; 
    for (ll i=2; i<=MAX; i++) func(i, v[i].div);
        
    int T; cin >> T;
    while (T--) {
        ll N; cin >> N;
        cout << v[N].g << '\n';
    }

    return 0;
}