ARC067 C - Factors of Factorial

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    cnt = [0] * N
    for i in range(2, N + 1):
        x = i
        for j in range(2, i + 1):
            while x % j == 0:
                x //= j
                cnt[j - 1] += 1
            if x == 1: break

    ret = 1
    for r in cnt:
        ret *= r + 1
        ret %= MOD
    print(ret)


if __name__ == '__main__':
    main()

考え方

整数Nの階乗から約数を求めるためには、
整数Nの階乗の値を全て分解し、構成する値の数を使うか否か、
つまり、組み合わせから約数を求めることが出来る。
例えば、整数6の階乗720は
6 * 5 * 4 * 3 * 2 = 3 * 2 * 5 * 2 * 2 * 3 * 2 = 2^4 * 3^2 * 5^1となる。
2を4回、3を2回、5を1回使用しているので、
これらを使うか否かの組み合わせから
(4 + 1) * (2 + 1) * (1 + 1) = 30のため、整数6の階乗の約数は30となる。

実装は要素をN個もった配列を用意しておき、
2からNまでの値を全て割る。
配列のindexを整数Nの階乗を構成する値と見立て、
2からNまでの値を割ることが出来る値の数を求める。
あとは算出した値の個数の組み合わせから約数の個数を求める。
なお、1は乗算と除算どちらにも影響しないため考慮しない。