我们需要判断正整数 N 能否拆分为一个镜像数 P 和一个完全平方数 Q=k2 的和,并且在所有可行方案中,要求 Q 尽可能小。
由于 Q 是完全平方数,可以从小到大枚举 k=1,2,…,令 Q=k2,直到 k2>N。对于每个 Q,计算 P=N−Q,然后检查 P 是否为镜像数(即将数字反转后与原数相等)。若 P 是镜像数,则当前 Q 就是所有可行方案中最小的完全平方数(因为 k 是从小到大枚举的),直接按要求输出并结束程序。
若枚举完所有可能的 Q 后仍未找到满足条件的 P,则说明 N 不是星光数,输出 NO。
判断一个整数是否为镜像数,可以将其转换为字符串,然后检查该字符串是否与其反转后的字符串相等。
小蓝定义了一种有趣的数字性质。
现在给定一个正整数 N,请你判断它是否为星光数。如果是,你需要找出一种满足条件的拆分方式,并要求完全平方数 Q 尽可能小。
输入的整数 N 满足 1≤N≤105。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册