Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
using uint32 = unsigned int;
using uint64 = unsigned long long;
uint64 divcnt3(uint64 n) {
const uint32 v = static_cast<uint32>(sqrtl(n));
std::vector<uint64> scnt(v + 1), lcnt(v + 1);
std::vector<uint32> primes;
for (uint32 i = 1; i <= v; ++i) {
scnt[i] = i - 1;
lcnt[i] = n / i - 1;
}
for (uint32 p = 2; p <= v; ++p) {
if (scnt[p] == scnt[p - 1]) continue;
primes.push_back(p);
const uint64 pcnt = scnt[p - 1];
const uint64 q = (uint64)p * p;
const uint32 ed = std::min<uint64>(v, n / q);
for (uint32 i = 1, w = v / p; i <= w; ++i) {
const uint32 d = i * p;
lcnt[i] -= lcnt[d] - pcnt;
}
if (n / p < std::numeric_limits<uint32>::max()) {
const uint32 m = n / p;
for (uint32 i = v / p + 1; i <= ed; ++i) {
uint32 d = m / i;
lcnt[i] -= scnt[d] - pcnt;
}
} else {
const uint64 m = n / p;
for (uint32 i = v / p + 1; i <= ed; ++i) {
uint32 d = m / i;
lcnt[i] -= scnt[d] - pcnt;
}
}
for (uint32 i = v; i >= q; --i) {
const uint32 d = i / p;
scnt[i] -= scnt[d] - pcnt;
}
}
primes.push_back(v + 1);
std::function<uint64(uint64, uint32, uint64)> rec = [&](uint64 rest, uint32 last, uint64 mul) {
uint64 t = (rest > v ? lcnt[n / rest] : scnt[rest]) - scnt[primes[last] - 1];
uint64 ret = mul * t * 4;
for (uint32 i = last; i < primes.size(); ++i) {
uint32 p = primes[i];
if (uint64(p) * p > rest) break;
for (uint64 q = p, nrest = rest, nmul = mul * 4; q * p <= rest; q *= p) {
ret += rec(nrest /= p, i + 1, nmul);
nmul += mul * 3;
ret += nmul;
}
}
return ret;
};
uint64 ret = 1;
if (n > 1) ret += rec(n, 0, 1);
return ret;
}
int main() {
int T;
scanf("%d", &T);
for (int cas = 1; cas <= T; ++cas) {
uint64 n;
scanf("%llu", &n);
printf("%llu\n", divcnt3(n));
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment