AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ARC034 C - 約数かつ倍数

問題原文

atcoder.jp

解法

制約が本質。
↓こういう感じになってる。

f:id:AT274:20200608202814p:plain

実際に約数の個数を考える必要があるのは、  B! より上の部分。
これは最大でも100個なので、それぞれについて素因数分解しても全然間に合う。

実装

from collections import Counter
A, B = map(int, input().split())
MOD = 1e9 + 7
C = Counter([])


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


for n in range(B + 1, A + 1):
    table = prime_factorization(n)
    C += Counter(table)

ans = 1
for v in C.values():
    ans *= (v + 1)
    ans %= MOD

print(int(ans % MOD))

感想

まぁこれはサクサク。
なんかもっと綺麗な図を書きたいのでタッチパッド的なやつが欲しくなる。