如何在O(√N)时间复杂度下求解满足x²-y为完全平方数的(x,y)对数量

承接你已完成的推导，我们可以基于变量q的枚举实现O(√N)复杂度的算法，步骤如下：

• 由y = pq ≥ 1且p ≥ q（因为z=(p-q)/2 ≥ 0，z是完全平方数的非负底数），可得q² ≤ pq ≤ N，因此q的取值范围仅为1 ≤ q ≤ √N，枚举规模直接控制在O(√N)量级。
• 你之前列出的约束(p+q)/2 ≤ N是冗余的：因为pq ≤ N且q≥1，因此p ≤ N/q ≤ N，代入可得(p+q)/2 ≤ (N + N)/2 = N，自动满足条件，无需额外判断。
• 对每个枚举的q，p的有效范围为[q, floor(N/q)]，只需要统计该区间内和q奇偶性相同的整数个数，累加所有q对应的个数即可得到最终答案。

设当前枚举的q对应的p上下界为L = q，R = floor(N/q)：

• 若R < L，当前q无有效p，贡献为0
• 若q为偶数，统计区间内偶数的个数：count = R//2 - (L-1)//2
• 若q为奇数，统计区间内奇数的个数：count = (R + 1)//2 - L//2

def count_pairs(N):
    ans = 0
    max_q = int(N ** 0.5)
    for q in range(1, max_q + 1):
        R = N // q
        if R < q:
            continue
        if q % 2 == 0:
            cnt = R // 2 - (q - 1) // 2
        else:
            cnt = (R + 1) // 2 - q // 2
        ans += cnt
    return ans

以N=3为例，max_q=1：

• q=1（奇数），R=3//1=3，cnt=(3+1)//2 - 1//2 = 2 - 0 = 2，对应两对(1,1)、(2,3)，和实际结果一致。

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