Submission #1069409


Source Code Expand

#!/usr/bin/env python3

import collections
import functools
import math
import operator


P = 1000000007


def sieve_of_eratosthenes(end):
    assert end > 1
    is_prime = [True for _ in range(end)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_fact(n, primes):
    factors = collections.Counter()
    if n < 2:
        return factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            factors[p] += 1
            n //= p
    if n > 1:
        factors[n] += 1
    return factors


def sum_ctrs(counters):
    return functools.reduce(operator.add, counters, collections.Counter())


def prod_mod(iterable, mod=P):
    def multi_mod(x, y):
        return (x % mod) * (y % mod) % mod
    return functools.reduce(multi_mod, iterable, 1)


def sum_of_divs_of_fact(n, mod=P):
    primes = sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1)
    ctr = sum_ctrs(factorize_fact(x, primes) for x in range(1, n + 1))
    ans = prod_mod(v + 1 for v in ctr.values()) % mod
    return ans


def main():
    print(sum_of_divs_of_fact(int(input())))


if __name__ == '__main__':
    main()

Submission Info

Submission Time
Task C - Factors of Factorial
User hamukichi
Language Python (3.4.3)
Score 300
Code Size 1397 Byte
Status AC
Exec Time 83 ms
Memory 3700 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 7
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All subtask_1_certain_01.txt, subtask_1_certain_02.txt, subtask_1_certain_03.txt, subtask_1_certain_04.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 30 ms 3700 KB
sample_02.txt AC 29 ms 3700 KB
sample_03.txt AC 82 ms 3700 KB
subtask_1_certain_01.txt AC 28 ms 3700 KB
subtask_1_certain_02.txt AC 28 ms 3700 KB
subtask_1_certain_03.txt AC 81 ms 3700 KB
subtask_1_certain_04.txt AC 83 ms 3700 KB
subtask_1_rand_01.txt AC 47 ms 3700 KB
subtask_1_rand_02.txt AC 51 ms 3700 KB
subtask_1_rand_03.txt AC 41 ms 3700 KB