競プロ典型 90 問：075 - Magic For Balls（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/10/31
• 結果：解けた
• 時間：5分

考えたこと

• まずは素因数分解する。いちばん効率が良いのは、 の を一番効率よく分割するのは、との素因数の数が同じになるようにすること。
• 素因数分解はいぜんにライブラリ化してある
• 最も効率よく分割すると、素因数の数をとして、 を切り上げた回数になる。
• スルッと解けてよかったけど、少数計算の誤差は不安かも。きにせず投げたらAC。

公式解説

https://twitter.com/e869120/status/1408195203538690048

解説を読んだふりかえり

• 答えは[2 ^ {x} >= K]を満たす最小のとのこと。logだと小数の誤差が不安だから、整数計算のほうが良いと思った。

ソース

from math import ceil, log2
N = int(input())

# 素因数分解
# prime_decomposition(24)     # --> [2, 2, 2, 3]
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

L = prime_decomposition(N)
ans = ceil(log2(len(L)))

print(ans)