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 |
|
|
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 |