正经题解｜N - 平方数

题目分析

可以将所有，可能会用到的完全平方数，先存下来，用于枚举等式中的 $a^2$。

$b ^ 2$，可以通过 $N - a ^ 2$ 得到，若 $N - a ^ 2$ 为完全平方数，则可以找到答案。

AC 代码

#include <bits/stdc++.h>
using namespace std;
vector<long long> v;
bool check(int c) {
    for(long long &i:v) {
        long long k = c - i;
        if (k < 0)return false;
        long long b = sqrt(k);
        if (b * b == k) {
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    for(long long i=0;i * i <= INT_MAX;i++) {
        v.push_back(i * i);
    }
    int t,n;
    cin >> t;
    while(t--) {
        cin >> n;
        if (check(n)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

复杂度分析

所有可能会用到的完全平方数的个数为 $\sqrt{N}$，时间复杂度为 $O(T \times \sqrt{N})$。