Python3で解く AtCoder Beginner Contest 114 D - 756

階乗の約数のカウント、七五数のカウント。愚直に約数を列挙して数え上げるとだめで数え上げに組み合わせのを考えながら工夫が必要な、いい問題

目次

概要

問題

• が与えられる。
• の約数の中に七五数は何個ある？
• 七五数とは約数をちょうど75個持つ正の整数とする。

---

解くときに考えた内容

• 約数のカウントは以下のように考える。

  • が素数とすると
  • の形でなにかの数字が表せるとすると、
  • がその約数の数

• の約数の中に七五数は何個あるで、約数を列挙して、それぞれの約数の数をカウントすると、TLEになってしまう。列挙せずに組み合わせのパターンで考える必要がある。

• の素数の数の数え上げを行う。

• 七五数はでいうと、
• 
  • となるようなの数
• 
  • となるようなの数 x （ となるようなの数 ）（以上になるなので、片側に含まれたらもう片側に含めたくないので）
• 
  • となるようなの数 x （ となるようなの数 )
• 
  • となるようなの数 x （ となるようなの数 ） x （となるようなの数 ） を で割る
• で,するのは、ある数以上あるものとしているので、該当の素数たちのなかから一度選んだものを排除したい。
• の時2で割るのは、累乗が4以上になる素数が10個ある時に二つ選ぶ選び方なので

---

コード

# 階乗の素数のカウント用
def factorization_list(n):
    tmp = n
    i = 2
    while i*i <= n:
        if tmp%i == 0:
            cnt = 0
            # 割れる場合は割れなくなるまで同じ数でわる
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            e[i] += cnt
        i += 1
    # 最後1になるか素数が余るので素数ならリストに追加
    if tmp != 1:
        e[tmp] += 1
    # nが1以外の素数だったら
    if e == [0] * (n+1):
        if n != 1:
            e[n] += 1
    return e
# m以上の個数（たとえばeの中に4以上のものがいくつあるかを調べる）    
def e_count(m):
    l = [i for i in e if i >= m]
    return (len(l))
n = int(input())
e = [0] * (n+1)
for i in range(2, n+1):
    factorization_list(i)
    # print(e)
# nが与えられた時に、1-indexでn!の素数の累乗の合計を示す。
# n=6
# 2! [0, 0, 1, 0, 0, 0, 0] 
# 3! [0, 0, 1, 1, 0, 0, 0]
# 4! [0, 0, 3, 1, 0, 0, 0]
# 5! [0, 0, 3, 1, 0, 1, 0]
# 6! [0, 0, 4, 2, 0, 1, 0]

# 重複しないようにうまくカウント、e_countはm以上だから一度選んだものを選ばないようにする
# 同じ値のものを選ぶときは選び方的に割り算する（mが4以上をを２つ選ぶ選び方のこと）
print(e_count(74) + \
    e_count(24) * (e_count(2)-1) + \
    e_count(14) * (e_count(4)-1) + \
    e_count(4)  * (e_count(4)-1) // 2 * (e_count(2)-2))def factorization_list(n):
    tmp = n
    i = 2
    while i*i <= n:
        if tmp%i == 0:
            cnt = 0
            # 割れる場合は割れなくなるまで同じ数でわる
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            e[i] += cnt
        i += 1
    # 最後1になるか素数が余るので素数ならリストに追加
    if tmp != 1:
        e[tmp] += 1
    # nが1以外の素数だったら
    if e == [0] * (n+1):
        if n != 1:
            e[n] += 1
    return e
# m以上の個数（たとえばeの中に4以上のものがいくつあるかを調べる）    
def e_count(m):
    l = [i for i in e if i >= m]
    return (len(l))
n = int(input())
e = [0] * (n+1)
# nが与えられた時に、1-indexでn!の素数の累乗の合計を示す。
# n=6
# 2! [0, 0, 1, 0, 0, 0, 0] 
# 3! [0, 0, 1, 1, 0, 0, 0]
# 4! [0, 0, 3, 1, 0, 0, 0]
# 5! [0, 0, 3, 1, 0, 1, 0]
# 6! [0, 0, 4, 2, 0, 1, 0]
for i in range(2, n+1):
    factorization_list(i)
    print(e)
# 重複しないようにうまくカウント、e_countはm以上だから一度選んだものを選ばないようにする
# 同じ値のものを選ぶときは選び方的に割り算する（mが4以上をを２つ選ぶ選び方のこと）
print(e_count(74) + \
    e_count(24) * (e_count(2)-1) + \
    e_count(14) * (e_count(4)-1) + \
    e_count(4)  * (e_count(4)-1) // 2 * (e_count(2)-2))

---

参考になる書籍

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

７章までは別記事に残してある。 blacktanktop.hatenablog.com