問題
三角数は、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
例
入力:
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 です。
入力:
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用に調整されています。上記の説明と制約に従ってください。