C++,DFS暴力打表出结论

#include <iostream>
#include <unordered_set>
#include <cmath>
using namespace std;

unordered_set<long long> visited; // 记录已访问过的数量，避免重复搜索
const long long MAX_LIMIT = 1000000; // 搜索上限（根据规律，足够验证小范围结果）

// DFS递归：当前拥有curr根，判断能否达到target
bool dfs(long long curr, long long target) {
    if (curr == target) return true; // 找到目标
    if (curr > target || curr > MAX_LIMIT) return false; // 超出范围，剪枝
    if (visited.count(curr)) return false; // 已访问过，剪枝
    
    visited.insert(curr); // 标记为已访问
    
    // 尝试分裂：将1根分裂为k²根（k≥2），新数量为curr-1 + k²
    for (long long k = 2; ; k++) {
        long long square = k * k;
        long long next = curr - 1 + square;
        
        if (next > target + MAX_LIMIT) break; // 超出合理范围，停止尝试更大的k
        if (dfs(next, target)) return true; // 递归搜索
    }
    
    return false;
}

bool canReach(long long x) {
    if (x == 1) return true; // 初始状态
    visited.clear(); // 每次调用清空访问记录
    return dfs(1, x);
}

int main() {
    // 测试
    for (long long x = 1; x <= 4000; x++) {
        cout << "x=" << x << " : " << (canReach(x) ? "Yes" : "No") << endl;
    }
    return 0;
}

AI写的 我太菜了 ==