# Project Euler #211: Divisor Square Sum

I started doing hackerrank problems only recently and here's my attempt to solve this problem.

Basically, you're given two integers N and K, so you need to find the sum of all 1 <= n <= N such that the sum is at most K away from a perfect square.

For example, for N = 65 and K = 0, we calculate the sum of squares of factors for all numbers from 1 to 65, i.e. 1, 5, 10, ... and see which of these sums is a perfect square (or more precisely 0 away from a perfect square). For 65, that happens to be 1 and 42, so the answer would be 43.

#include <cmath>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

// Lookup table
unordered_map<uint_fast16_t, uint_fast16_t> fac_sq_diff;

auto sum_fac_sq(uint_fast16_t n) {
uint_fast16_t sum = 0;
// Calculate factors in pairs,
// eg. 20 => (1, 20), (2, 10), (4, 5)
auto sqrtn = sqrt(n);
for (auto i = 1; i <= sqrtn; ++i) {
if (n % i == 0) {
sum += (i * i);
auto j = n / i;
if (i != j) {
sum += (j * j);
}
}
}
return sum;
}

uint_fast32_t solve(uint_fast16_t n, uint_fast16_t k) {
uint_fast32_t result = 0;
int_fast32_t diff = 0;
for (uint_fast16_t j = 1; j <= n; ++j) {
auto idiff = fac_sq_diff.find(j);
if (idiff == fac_sq_diff.end()) {
auto sum = sum_fac_sq(j);
// Closest perfect square:
// https://stackoverflow.com/questions/6054909
auto sqrtsum = static_cast<uint_fast16_t>(sqrt(static_cast<float>(sum)) + .5f);
diff = sum - (sqrtsum * sqrtsum);
diff = abs(diff);
idiff = fac_sq_diff.emplace(j, diff).first;
}

if (idiff->second <= k) {
result += j;
}
}
return result;
}

int main() {
// Expected input:
// 11
// 65 0
// 269 1
// 312 2
// 745 3
// 1457 4
uint_fast16_t q = 1;
cin >> q;

// Find max N and reserve lookup table mem
vector<pair<uint_fast16_t, uint_fast16_t>> NK;
uint_fast16_t max_N = 0;
for (auto i = 0; i < q; ++i) {
uint_fast16_t N = 0, K = 0;
cin >> N >> K;
NK.emplace_back(N, K);
max_N = max(N, max_N);
}
fac_sq_diff.reserve(max_N);

for (auto &nk: NK) {
cout << solve(nk.first, nk.second) << endl;
}
return 0;
}


No matter what I try, I am not able to get past the first test (in terms of speed). :(

I also tried the geometric summation formula to calculate the sum of factors squared, but my implementation turned out to be slower than this one.

## 1 Answer

As always, before tackling the Project Euler problems, do your math homework. Few hints:

• Do not brute force. $\sigma_2(n)$ is multiplicative. That allows it to be computed in a much more efficient way.

• Do not throw away your work. $\sigma_2(n)$ does not depend on $k$. Tabulate it once toward the maximal possible $N$, or extend it as $N$ grows.

Besides that, the constraints say $1 < N < 6\cdot 10^6, 0 < K < 10^6$. uint_16 is surely insufficient.

• +1 especially for reviewing the code and algorithm without revealing a complete solution and leaving the fun of discovery intact. – Edward Jul 13 '18 at 20:46
• Very helpful information, particularly regarding the multiplicative function. I think I'm back on track, thanks to you. – user3490458 Jul 14 '18 at 10:12