問題
数を 2 乗し、その 10 進数の桁を 2 つに分けます。もとの数の桁数を d としたとき、右側の部分は末尾の d 桁、左側の部分は残りの桁です(何も残らなければ 0 とします)。右側の部分が 0 でなく、2 つの部分の和がもとの数に等しいとき、その数をカプレカ数と呼びます。たとえば 297 は 3 桁で、297² = 88209 です。右側の部分は 209、左側の部分は 88 で、88 + 209 = 297 になります。
kaprekar_number(n) を実装してください。
カプレカ数の定義は資料によって異なります。この問題では、分ける位置を常に右から d 桁のところに固定します(OEIS A053816 に載っている定義で、Wikipedia の定義では p = d の場合にあたります)。ほかの位置で分けることも認める資料もあり、その場合は 4879 のような数もカプレカ数になりますが、この問題の定義ではカプレカ数ではありません。右側の部分は先頭に 0 があってもかまいません(703 なら 703² = 494209 から 494 と 209 になります)。また、右側の部分は 0 であってはならないので、10, 100, ... はカプレカ数ではありません。1 はカプレカ数です。1² = 1 なので、左側は 0、右側は 1 になります。
入力
n: 判定する数。
出力
n が上の定義でカプレカ数なら true、そうでなければ false を返してください。
制約
1 ≤ n ≤ 10^9
例
入力:
n = 45
期待される出力:
expected = True
入力:
long long n = 45;
期待される出力:
bool expected = true;
入力:
long n = 45;
期待される出力:
bool expected = true;
解説
45 は 2 桁で、45² = 2025 です。左側の部分は 20、右側の部分は 25 で、20 + 25 = 45 なので、答えは true です。
入力:
n = 4879
期待される出力:
expected = False
入力:
long long n = 4879;
期待される出力:
bool expected = false;
入力:
long n = 4879;
期待される出力:
bool expected = false;
解説
4879 は 4 桁で、4879² = 23804641 です。左側の部分は 2380、右側の部分は 4641 で、2380 + 4641 = 7021 は 4879 ではないので、答えは false です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
n の桁数を d とし、n² は 64 ビット整数で扱いましょう。
ヒント 2
p = 10^d とすると、右側の部分は n² mod p、左側の部分は n² / p です。
ヒント 3
和が一致しても、右側の部分が 0 ならカプレカ数ではありません。
目安の計算量
時間 O(d)(d は桁数)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。