問題
n! = 1 × 2 × ... × n はどんなべき乗よりも速く大きくなり、25! ですでに26桁あります。n! を正確に求め、その各桁の和を計算してください。多倍長整数が使えない場合は、数を桁の配列として持ち、2, 3, ..., n を順に掛けていきます。
factorial_digit_sum(n) を実装してください。
入力
n:階乗を求める数。
出力
n! の各桁の和を返してください。0! = 1 であることに注意しましょう。
制約
0 ≤ n ≤ 1000
例
例 1
入力:
n = 5
期待される出力:
expected = 3
入力:
long long n = 5;
期待される出力:
long long expected = 3;
入力:
long n = 5;
期待される出力:
long expected = 3;
解説
5! = 120 で、1 + 2 + 0 = 3 です。
例 2
入力:
n = 0
期待される出力:
expected = 1
入力:
long long n = 0;
期待される出力:
long long expected = 1;
入力:
long n = 0;
期待される出力:
long expected = 1;
解説
0! は定義により 1 なので、答えは 1 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
1 から始めて、2, 3, ..., n を順に掛けます。
ヒント 2
各桁に掛けて繰り上がりを足し、一の位を残して残りを繰り上げます。
ヒント 3
最後に繰り上がりが残っていれば、それが新しい桁になります。
目安の計算量
時間 O(n × D)(D は n! の桁数)、追加メモリ O(D)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。