Soluion of UVA problem: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2421

11426 - GCD - Extreme (II).cpp

#include <iostream>
#include <math.h>

using namespace std;

#define FOR(i, L, U) for(int i=(int)L; i<=(int)U; i++)
#define FORD(i, U, L) for(int i=(int)U; i>=(int)L; i--)

#define READ(x) freopen(x, "r", stdin)
#define WRITE(x) freopen(x, "w", stdout)

#define PB push_back

typedef unsigned long long ULL;

inline int src() { int ret; scanf("%d", &ret); return ret; }

#define MAX 1000000

uint bigPrime[MAX + 7];
ULL gcdSum[MAX + 7];
ULL DP[MAX + 7];

// Main idea for faster pre cal is to use result of previous gcdSum.
// Suppose we need to calc gcdSum(12), then we can use result of gcdSum(4)
// and multiply formula part for prime 3.
void preCal() {
    memset(bigPrime, -1, sizeof bigPrime);

    for (int i = 2; i <= MAX; ++i) {
        if (bigPrime[i] == -1) {
            bigPrime[i] = i;
            // Only for primes up to root of MAX
            if (i <= 2000)
                for (int j = i*i; j <= MAX; j += i) bigPrime[j] = i;
        }
    }

    gcdSum[1] = 1;
    DP[1] = 0;
    for (int i = 2; i <= MAX; ++i) {
        int p = bigPrime[i];
        int a = 0;
        ULL pa = 1;
        int tmp = i;

        while (tmp % p == 0) {
            a++;
            pa *= p;
            tmp /= p;
        }
        gcdSum[i] = ((a+1) * pa - a * (pa / p)) * gcdSum[tmp];
        DP[i] = DP[i-1] + gcdSum[i] - i;
    }
}

int main()
{
    //READ("input.txt");
    //WRITE("output.txt");
    int i, j, k;
    int TC, tc;
    double cl = clock();

    preCal();

    int n;

    while (scanf("%d", &n) == 1) {
        if (n == 0) break;

        printf("%llu\n", DP[n]);
    }

    cl = clock() - cl;
    fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC);

    return 0;
}