ARC034 C - 約数かつ倍数
問題原文
解法
制約が本質。
↓こういう感じになってる。
実際に約数の個数を考える必要があるのは、 より上の部分。
これは最大でも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))
感想
まぁこれはサクサク。
なんかもっと綺麗な図を書きたいのでタッチパッド的なやつが欲しくなる。