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

約数の多い三角数

約数を d 個以上持つ最初の三角数を求めます。

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

  • 素因数分解から約数の個数を求められる
  • 三角数の公式を使える
  • 互いに素な因数の積に分けて考えられる

問題

原文(英語)を表示

三角数は、1 個、2 個、3 個、... と点を段ごとに並べてできる三角形の点の総数で、T(1) = 1, T(2) = 3, T(3) = 6, T(k) = k(k + 1) / 2 です。小さい順に調べていき、正の約数(1 とその数自身も含みます)を d 個以上持つ最初の三角数を見つけてください。

highly_divisible_triangular(d) を実装してください。

大きなケースでは、約数を1つずつ数えていては間に合いません。代わりに素因数分解しましょう。n = p^a × q^b × ... なら、約数の個数は (a + 1)(b + 1)... です。k と k + 1 は共通の因数を持たないので、別々に素因数分解できます。

入力

d:必要な約数の個数。

出力

約数を d 個以上持つ最初の三角数を返してください。

制約

1 ≤ d ≤ 300

例

例 1
入力:
d = 4

期待される出力:
expected = 6
入力:
long long d = 4;

期待される出力:
long long expected = 6;
入力:
long d = 4;

期待される出力:
long expected = 6;

解説

1 の約数は1個、3 は2個ですが、6 は4個(1, 2, 3, 6)なので、答えは 6 です。

例 2
入力:
d = 9

期待される出力:
expected = 36
入力:
long long d = 9;

期待される出力:
long long expected = 36;
入力:
long d = 9;

期待される出力:
long expected = 36;

解説

28 の約数は6個で、36 = 2² × 3² は 3 × 3 = 9 個(1, 2, 3, 4, 6, 9, 12, 18, 36)なので、答えは 36 です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

T(k) = k(k + 1) / 2 で、k と k + 1 には共通の因数がありません。

ヒント 2

k と k + 1 のうち偶数のほうを半分にし、それぞれの約数の個数を数えます。

ヒント 3

互いに素な数の積の約数の個数は、それぞれの約数の個数の積です。

目安の計算量

時間 O(K √K)(K は試す三角数の個数)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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