无需遍历x、y求解√x+√y=√(c²n)？代码出错求排查

首先明确方程变形：
原方程 √x + √y = √(c²n) 可简化为 √x + √y = c√n（因为√(c²n)=c√n，c是正整数）。

无需遍历的求解思路 #

要得到正整数x、y，只需让√x和√y都是√n的整数倍：

• 设 √y = k√n（k是1到c-1之间的任意正整数），则 √x = c√n - k√n = (c - k)√n
• 平方后得到：y = k²n，x = (c - k)²n

这两个数必然是正整数，完全符合要求，全程无需遍历，直接计算即可。

你尝试的y=n的情况 #

当k=1时，y=n，x=(c-1)²n，这个推导是正确的。代码出错大概率是数据类型溢出或格式/变量定义错误：

• 若用32位int存储：c是1e9，(c-1)²是1e18，远超int上限（约2e9），必须用64位整数类型，比如C++里的long long或unsigned long long。
• 检查是否输出格式错误：比如用%d输出64位整数，应该用%lld或%I64d（视编译器而定）。
• 题目明确c²n ≤1e18，而(c-1)²n ≤c²n ≤1e18，64位整数完全能容纳这个结果。

示例C++代码片段 #

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long c, n;
        cin >> c >> n;
        long long k = 1; // 取k=1，也可以选其他1<=k<c的正整数
        long long y = k * k * n;
        long long x = (c - k) * (c - k) * n;
        cout << x << " " << y << "\n";
    }
    return 0;
}

该代码处理1e5组测试用例完全符合时间要求，每组都是O(1)计算。

内容的提问来源于stack exchange，提问作者Youssef Emad