問題

解法

素因数分解してみる

$N \leq 100$ かつ 100以下の最大の素数は97より、 $N!$ を素因数分解すると、 $2^{p_2} \cdot 3^{p_3} \cdot \cdots \cdot 97^{p_{97}}$ のように素数のべき乗の積で表せます。ここで、 $p_2, p_3, \ldots, p_{97}$ は0以上の整数です。 $N!$ の約数は、整数の組 $0 \leq q_2 \leq p_2, 0 \leq q_3 \leq p_3, \ldots, 0 \leq q_{97} \leq p_{97}$ を用いて、 $2^{q_2} \cdot 3^{q_3} \cdot \cdots \cdot 97^{q_{97}}$ のように素数のべき乗の積で表されます。

七五数を満たすパターン

さて、約数をちょうど75個持つ $N!$ の約数について、 $q_2, q_3, \ldots, q_{97}$ はどのような整数の組になるでしょうか。まず、 $2^{q_2} \cdot 3^{q_3} \cdot \cdots \cdot 97^{q_{97}}$ の約数の個数は $(q_2 + 1)(q_3 + 1)\cdots(q_{97} + 1)$ です。また、75をいくつかの数の積で表すと $75=25 \cdot 3 = 15 \cdot 5 = 5 \cdot 5 \cdot 3$ となります（順序が異なるものは省略）。したがって、 $(q_2 + 1)(q_3 + 1)\cdots(q_{97} + 1)$ が以下のいずれかのパターンを成す場合に、約数をちょうど75個持ちます。

パターン1: $(74 + 1)$
パターン2: $(24 + 1) \cdot (2 + 1)$
パターン3: $(14 + 1) \cdot (4 + 1)$
パターン4: $(4 + 1) \cdot (4 + 1) \cdot (2 + 1)$

パターン1の個数

パターン1を満たす $q_2, q_3, \ldots, q_{97}$ の組数は、 $p_2, p_3, \ldots, p_{97}$ のうち、74以上である値の個数です。

パターン2の個数

パターン2を満たす $q_2, q_3, \ldots, q_{97}$ の組数は、以下の積です。

$p_2, p_3, \ldots, p_{97}$ のうち、24以上である値の個数
（ $p_2, p_3, \ldots, p_{97}$ のうち、2以上である値の個数） - 1

パターン3の個数

パターン3を満たす $q_2, q_3, \ldots, q_{97}$ の組数は、以下の積です。

$p_2, p_3, \ldots, p_{97}$ のうち、14以上である値の個数
（ $p_2, p_3, \ldots, p_{97}$ のうち、4以上である値の個数） - 1

パターン4の個数

パターン4を満たす $q_2, q_3, \ldots, q_{97}$ の組数は、以下の積です。

( のうち、4以上である値の個数 * (（のうち、4以上である値の個数） - 1)) / 2
- 4以上のpを2つ選ぶ組み合わせです
（ $p_2, p_3, \ldots, p_{97}$ のうち、2以上である値の個数） - 2

求める解

パターン1, 2, 3, 4の個数の和が求める解です。

ACしたコード

N = int(input())
p = [
    sum(N // (i**k) for k in range(1, 8))
    for i in range(2, 97 + 1)
    if all(i % j != 0 for j in range(2, i))
]
def f(m):
  return len([i for i in p if i >= m])
ans = f(74) + f(24) * (f(2) - 1) + f(14) * (f(4) - 1) + f(4) * (f(4) - 1) * (f(2) - 2) // 2
print(ans)

024号文書

主にプログラミング

ABC114 D - 756

問題

解法