练46.4 第N个智慧数

解题思路

平方差为(a-b)(a+b)，两个因子同奇偶且a、b都正。所有奇数≥3可用连续整数平方差表示；4的倍数≥8可用相差2的整数平方差表示。1与4需用到0，排除。逐个计数到第n个。

正确性说明

平方模4只能是0或1，所以平方差不能为2模4；其余奇数和4倍数由给定构造覆盖，去掉不可用正整数构造的1、4后条件充分必要。

易错点

题目要求两个正整数，所以不能把1、4计入。

复杂度

时间O(n)，空间O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int count = 0;
    for (int x = 1;; x++) {
        if ((x >= 3 && x % 2 == 1) || (x >= 8 && x % 4 == 0))
            count++;
        if (count == n) {
            cout << x << "\n";
            break;
        }
    }
    return 0;
}