Integers: Recreation One

• Time : $O(sum(\sqrt{m} ... \sqrt{n}))$
• Space : $O(1)$

c++

#include <bits/stdc++.h>
using namespace std;

class SumSquaredDivisors
{
public:
    static std::vector<std::pair<long long, long long>> listSquared(long long m, long long n);
};
long long get(long long x) {
    long long res = 0;
    for(long long i = 1; i * i <= x; i++) {
        if(x % i) continue;
        res += i * i;
        if(i * i != x) res += (x / i) * (x / i);
    }
    return res;
}
vector<pair<long long, long long>> SumSquaredDivisors::listSquared(long long m, long long n) {
    vector<pair<long long, long long>> res;
    for(long long i = m; i <= n; i++) {
        long long squareSum = get(i);
        long long sq = sqrt(squareSum);
        if(sq * sq == squareSum) res.push_back({i,squareSum});
    }
    return res;
}