小红的好数

[题目链接](https://www.nowcoder.com/practice/a4e3706a856644289a7a60b8d93fa5fc)

思路

一个整数 $n$ 是"好数"，当且仅当存在一种拆分方式，使得 $n = p + s$ ，其中 $p$ 是回文数， $s$ 是完全平方数（ $s \geq 0$ ）。

枚举完全平方数

枚举所有满足 $s = i^2 \leq n$ 的完全平方数，判断 $p = n - s$ 是否为回文数：

从 $i = 0$ 开始，令 $s = i^2$ ；
计算 $p = n - s$ ；
判断 $p$ 是否为回文数（将数字转为字符串，与其反转比较）；
若是，输出 YES 及 $p$ 和 $s$ ；若遍历完所有平方数都未找到，输出 NO。

复杂度分析

枚举平方数最多 $O(\sqrt{n})$ 次，每次判断回文数为 $O(\log n)$ ，总体复杂度 $O(\sqrt{n} \log n)$ 。

注意事项

$0$ 是合法的完全平方数（ $0 = 0^2$ ），需要包含在枚举范围内；
回文数需要 $\geq 0$ ，即 $n - s \geq 0$ ，枚举 $s \leq n$ 即满足；
题目允许输出任意合法答案。

样例演示

样例 1： $n = 2$

$i=0$ : $s=0$ , $p=2$ ，"2" 是回文数，输出 YES\n2 0（也可输出 1 1，均合法）

样例 2： $n = 35$

$i=0$ : $s=0$ , $p=35$ ，"35" 非回文
$i=1$ : $s=1$ , $p=34$ ，"34" 非回文
$i=2$ : $s=4$ , $p=31$ ，"31" 非回文
$i=3$ : $s=9$ , $p=26$ ，"26" 非回文
$i=4$ : $s=16$ , $p=19$ ，"19" 非回文
$i=5$ : $s=25$ , $p=10$ ，"10" 非回文
遍历结束，输出 NO

代码

C++

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

bool isPalindrome(long long x) {
    if (x < 0) return false;
    string s = to_string(x);
    string r = s;
    reverse(r.begin(), r.end());
    return s == r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;

    for (long long i = 0; i * i <= n; i++) {
        long long sq = i * i;
        long long rem = n - sq;
        if (rem >= 0 && isPalindrome(rem)) {
            cout << "YES" << endl;
            cout << rem << " " << sq << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    static boolean isPalindrome(long x) {
        if (x < 0) return false;
        String s = Long.toString(x);
        String r = new StringBuilder(s).reverse().toString();
        return s.equals(r);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        for (long i = 0; i * i <= n; i++) {
            long sq = i * i;
            long rem = n - sq;
            if (rem >= 0 && isPalindrome(rem)) {
                System.out.println("YES");
                System.out.println(rem + " " + sq);
                return;
            }
        }

        System.out.println("NO");
    }
}