The Sum and The Rest of Certain Pairs of Numbers have to be Perfect Squares (more Challenging)

• Time : $O(limit * log(\sqrt{limit}))$
• Space : $O(\sqrt{limit})$

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

std::vector<std::pair<unsigned int, unsigned int>> nClosest(const unsigned int n, const unsigned int k) {
    unsigned int lim = n * 2;
    vector<int> po;
    for(unsigned int i = 1; i * i <= lim; i++) po.push_back(i * i);
    vector<pair<unsigned int, unsigned int>> res;
    for(int i = n - 1; i >= 0 and res.size() < k; i--) {
        auto p = lower_bound(begin(po), end(po), i * 2 + 1) - begin(po);
        for(int j = p - 1; j >= 0 and res.size() < k and po[j] > i; j--) {
            unsigned int x = po[j] - i;
            if(x >= i) continue;
            unsigned int t = i - x, sq = sqrt(t);
            if(sq * sq == t) res.push_back({i,x});
        }
    }
    return res;
}