Project Euler #211: Divisor Square Sum

Question

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.

Answer 1

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.

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