数学とアルゴリズムの力で解くプログラミングの問題です。
- 全てプログラミングで解くことを想定した問題です。
- 正答を出力するコードを書いて下さい。
- 適切なアルゴリズムでコードを書けば、標準的なコンピュータで数秒以内の実行時間で正解が出せます。
- 作成者は ideone にて python で 1 秒未満で正解できることを確認しています。
コメント欄やブログでのネタバレ等はご自由に…。
A. 超階乗
自然数 n の階乗（n!）は、1 から n までの自然数の積と定義されます。
n! = 1×2×3×・・・×n
自然数 n の「超階乗」を「1 から n までの自然数の階乗の積」と定義します。
これを n$と書き表します。
n$ = (1!)×(2!)×(3!)×･･･×(n!)
例えば、4$ = 288 です。
4$ = (1!)×(2!)×(3!)×(4!) = 1×2×6×24 = 288
さて、4$が、3 で何回割り切れるかを考えてみましょう。
288 ÷ 3 ＝ 96
96 ÷ 3 ＝ 32
ですから、4$は 3 で最大 2 回割り切れます。
同様に、10$は、3 で最大 17 回割り切れることが確かめられます。
109$（10 億の超階乗）は、3 で最大何回割り切れるでしょうか？
B. 禁止数字
次の条件を満たす正の整数を⼩さい順に並べて数列を作ります。
「どの桁にも 0, 1, 2, 3 が表れない。」
つまり、下のような数列です。
4, 5, 6, 7, 8, 9, 44, 45, 46, 47, 48, 49, 54, 55, ...
この数列の 30 番⽬の項は 79 であることが確かめられます。
この数列の 109 番⽬の項を求めて下さい。
C. 多段べき乗
0 以上の整数 n に対し、数列 F(n) を次の漸化式で定義します。
F(0) ＝ 1
F(n+1) ＝ 3F(n)
つまり、下のような数列です。
1, 3, 27, 7625597484987, ...
F(109) の下 6 桁を求めて下さい。
D. 白黒連
⽩と⿊のマークを⼀列に並べます。
このとき、もっとも⻑い⿊の連続した個数を考えましょう。
例えば次の並べ⽅では、もっとも⻑い⿊の連続した個数は 4 個です。
◆◆◆◆◇◆
次の並べ⽅では、もっとも⻑い⿊の連続した個数は 3 個です。
◇◇◆◆◆◇◆◇◇◆◆◆◇◆◆
6 個を並べるとき、もっとも⻑い⿊の連続した個数が 4 個となるような並べ⽅は、全部で 5 通り
あります。
(1) ◆◆◆◆◇◆
(2) ◆◆◆◆◇◇
(3) ◆◇◆◆◆◆
(4) ◇◆◆◆◆◇
(5) ◇◇◆◆◆◆
自然数 n, m に対し、n 個のマークを並べるとき、もっとも⻑い⿊の連続した個数が m 個となるような並べ⽅の数を F(n, m) と定義します。
例えば、F(6, 4) = 5、F(12, 3) = 1167 であることが確かめられます。
F(105, 104) の下 6 桁を求めて下さい。
E. 最小公倍数
最⼩公倍数とは、2 つの整数の共通の倍数のうち最⼩のものです。
例えば、6 と 8 の最⼩公倍数は 24 です。
最⼩公倍数が 24 になるような数の組 (a,b) を考えましょう。
a≦b のとき、そのような組は全部で 11 組あることが分かります。
(1,24) (2,24) (3,8) (3,24) (4,24) (6,8)
(6,24) (8,12) (8,24) (12,24) (24,24)
自然数 n に対し、a≦b のとき、最⼩公倍数が n!（n の階乗）となるような組 (a, b) の個数を F(n) と定義します。
例えば、F(4) = 11、F(6) = 68 であることが確かめられます。
F(105) の下 6 桁を求めて下さい。