sparse.cpp

sparse.cpp

// $ g++ sparse.cpp --std=c++11
// $ time ./a.out
// sum(2000000000) = 95673602693282040
//
// real	0m0.150s
// user	0m0.147s
// sys	0m0.003s


#include <iostream>
#include <cmath>

using namespace std;

const long long n = 2000000000;
const int r = sqrt(n);
const int nprime = n / r - 1;
long long V[nprime + r + 1];
long long S[nprime + r + 1];

long long idx(long long i) {
    return (i <= nprime) ? i : nprime + r - n / i + 1;
}

long long gauss(long long i) {
    return i * (i + 1) / 2 - 1;
}

int main(int argc, char** argv) {
    for (int i = 1; i <= nprime; i++) {
        V[i] = i;
    }
    for (int i = 1; i <= r; i++) {
        V[nprime + i] = n / (r - i + 1);
    }
    for (int i = 1; i <= nprime + r; i++) {
        S[i] = gauss(V[i]);
    }
    for (int p = 2; p <= r; p++) {
        if (S[idx(p)] > S[idx(p - 1)]) {
            for (int i = nprime + r; i >= 1; i--) {
                const long long v = V[i];
                if (v < p * p) {
                    break;
                }
                S[idx(v)] -= p * (S[idx(v / p)] - S[idx(p - 1)]);
            }
        }
    }
    cout << "sum(" << n << ") = " << S[idx(n)] << endl;
    return 0;
}