Problem p03253 (python)

Fixed submission:
N,M=map(int,input().split())
mod=10**9+7

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
DICT=dict()
i=0
while M!=1:
    if M%Primes[i]==0:
        DICT[i]=DICT.get(i,0)+1
        M=M//Primes[i]
    elif i<len(Primes)-1:
        i+=1
    else:
        DICT[M]=1
        M=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(b-i,mod-2,mod)%mod

    return ANS%mod


ANS=1
for i in DICT.values():
    ANS=ANS*Combi2(N-1+i,i)%mod

print(ANS)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
mod=10**9+7

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
DICT=dict()
i=0
while M!=1:
    if M%Primes[i]==0:
        DICT[i]=DICT.get(i,0)+1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(b-i,mod-2,mod)%mod

    return ANS%mod


ANS=1
for i in DICT.values():
    ANS=ANS*Combi2(N-1+i,i)%mod

print(ANS)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
mod=10**9+7

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
LISTS=[0 for i in range(4000)]
i=0
while M!=1:
    if M%Primes[i]==0:
        LISTS[i]+=1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(b-i,mod-2,mod)%mod

    return ANS%mod


ANS=1
for i in range(4000):
    if LISTS[i]>=1:
        ANS=ANS*Combi2(N-1+LISTS[i],LISTS[i])%mod

print(ANS)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
mod=10**9+7

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
LISTS=[0 for i in range(4000)]
i=0
while M!=1:
    if M%Primes[i]==0:
        LISTS[i]+=1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(b-i,mod-2,mod)

    return ANS%mod


ANS=1
for i in range(len(LISTS)):
    if LISTS[i]>=1:
        ANS=ANS*Combi2(N-1+LISTS[i],LISTS[i])%mod

print(ANS)

Buggy submission (verdict: Runtime Error):
import itertools

N,M=map(int,input().split())

mod=10**9+7

#x以下の素数の列挙
    
import math

x=math.floor(math.sqrt(10**9))

L=math.floor(math.sqrt(x))#平方根を求める

Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

def fact(M):
    LIST=[]
    i=0
    while M!=1:
        if M%Primes[i]==0:
            LIST.append(Primes[i])
            M=M//Primes[i]
        else:
            i+=1

    PE=list(itertools.product(range(0,2),repeat=len(LIST)))

    SET={1}

    for pe in PE:
        ANS=1

        for j in range(len(LIST)):
            if pe[j]==1:
                ANS=ANS*LIST[j]

  

        SET=SET|{ANS}

    return SET

SET=fact(M)
factor=dict()

for j in SET:
    factor[j]=fact(j)

    
DP=dict()
def dp(n,m):
    if n==1 or m==1:
        return 1
    
    ANS=0
    for j in factor[m]:
        if DP.get((n-1,m//j),-1)!=-1:
            ANS=(ANS+DP[n-1,m//j])%mod
        else:
            ANS=(ANS+dp(n-1,m//j))%mod

    DP[n,m]=ANS%mod
    return ANS
    
for i in range(1,N,10):
    dp(i,M)

print(dp(N,M))