AtCoder Regular Contest 004

Submission #463366

Source codeソースコード

import math
MOD = 10**9+7
n, m = map(int, raw_input().split())
p = []
minus = 0
if n<0:
    minus = 1
    n = -n

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0
M = m+50
fact = [0] * (M+1)
frev = [0] * (M+1)
fact[0] = frev[0] = 1
for i in xrange(1, M+1):
    fact[i] = (i * fact[i-1]) % MOD
    c = extgcd(fact[i], MOD)[1]
    frev[i] = (c + MOD) % MOD
def comb(n, k):
    rr = (frev[n-k] * frev[k]) % MOD
    return (fact[n] * rr) % MOD

i = 2
sq = math.sqrt(n)
while n>1 and i<=sq:
    if n%i==0:
        cnt = 0
        while n%i==0:
            n /= i
            cnt += 1
        p.append(cnt)
        sq = math.sqrt(n)
    i += 1
if n>1:
    p.append(1)
ans = 1
for i in xrange(len(p)):
    ans = (ans * comb(p[i]+m-1, m-1)) % MOD
sig = 0
for i in xrange((m-minus)/2+1):
    sig = (sig + comb(m, 2*i+minus)) % MOD
ans = (ans * sig) % MOD
print ans

Submission

Task問題 D - 表現の自由 ( Freedom of expression )
User nameユーザ名 tjake
Created time投稿日時
Language言語 Python (2.7.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 994 Byte
File nameファイル名
Exec time実行時間 1299 ms
Memory usageメモリ使用量 9772 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_max.txt,00_max2.txt,00_max3.txt,00_min.txt,00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,01_rnd_00.txt,01_rnd_01.txt,01_rnd_02.txt,01_rnd_03.txt,01_rnd_04.txt,01_rnd_05.txt,01_rnd_06.txt,01_rnd_07.txt,01_rnd_08.txt,01_rnd_09.txt,01_rnd_10.txt,01_rnd_11.txt,01_rnd_12.txt,01_rnd_13.txt,01_rnd_14.txt,01_rnd_15.txt,01_rnd_16.txt,01_rnd_17.txt,01_rnd_18.txt,01_rnd_19.txt,01_rnd_20.txt,01_rnd_21.txt,01_rnd_22.txt,01_rnd_23.txt,01_rnd_24.txt,01_rnd_25.txt,01_rnd_26.txt,01_rnd_27.txt,01_rnd_28.txt,01_rnd_29.txt,04_primes_01.txt,04_primes_02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_max.txt AC 1260 ms 9772 KB
00_max2.txt AC 1286 ms 9732 KB
00_max3.txt AC 1267 ms 9764 KB
00_min.txt AC 56 ms 3380 KB
00_sample_01.txt AC 56 ms 3376 KB
00_sample_02.txt AC 57 ms 3376 KB
00_sample_03.txt AC 58 ms 3368 KB
00_sample_04.txt AC 69 ms 3492 KB
01_rnd_00.txt AC 544 ms 5924 KB
01_rnd_01.txt AC 206 ms 4124 KB
01_rnd_02.txt AC 76 ms 3492 KB
01_rnd_03.txt AC 509 ms 5680 KB
01_rnd_04.txt AC 453 ms 5424 KB
01_rnd_05.txt AC 579 ms 6060 KB
01_rnd_06.txt AC 224 ms 4260 KB
01_rnd_07.txt AC 251 ms 4388 KB
01_rnd_08.txt AC 1219 ms 9508 KB
01_rnd_09.txt AC 733 ms 6944 KB
01_rnd_10.txt AC 770 ms 7076 KB
01_rnd_11.txt AC 868 ms 7708 KB
01_rnd_12.txt AC 1105 ms 8996 KB
01_rnd_13.txt AC 584 ms 6180 KB
01_rnd_14.txt AC 683 ms 6696 KB
01_rnd_15.txt AC 270 ms 4512 KB
01_rnd_16.txt AC 890 ms 7724 KB
01_rnd_17.txt AC 1255 ms 9768 KB
01_rnd_18.txt AC 964 ms 8236 KB
01_rnd_19.txt AC 201 ms 4140 KB
01_rnd_20.txt AC 669 ms 6568 KB
01_rnd_21.txt AC 650 ms 6448 KB
01_rnd_22.txt AC 305 ms 4652 KB
01_rnd_23.txt AC 819 ms 7336 KB
01_rnd_24.txt AC 989 ms 8180 KB
01_rnd_25.txt AC 1155 ms 9188 KB
01_rnd_26.txt AC 732 ms 6952 KB
01_rnd_27.txt AC 545 ms 6004 KB
01_rnd_28.txt AC 585 ms 6176 KB
01_rnd_29.txt AC 1135 ms 9128 KB
04_primes_01.txt AC 1299 ms 9752 KB
04_primes_02.txt AC 1266 ms 9772 KB