中級 0件解決済み 正答率0%

カプレカ数

d 桁の数を 2 乗して左側の部分と d 桁の右側の部分に分けたとき、2 つの和がもとの数になるかどうかを判定します。

このチャレンジで学べること

  • ある桁の位置で数を左側と右側に分ける
  • n の桁数を使って分ける位置を決める
  • 0 でないという条件も含め、定義のすべての条件を確かめる

問題

原文(英語)を表示

数を 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

例

例 1
入力:
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 です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。