結果

問題 No.1973 Divisor Sequence
ユーザー Eguy
提出日時 2022-06-10 22:13:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 894 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 83,356 KB
最終ジャッジ日時 2024-09-21 06:27:04
合計ジャッジ時間 6,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, math
sys.setrecursionlimit(1000000)
INF = 1 << 100
mod = 1000000007
#mod = 998244353
input = lambda: sys.stdin.readline().rstrip()
li = lambda: list(map(int, input().split()))

def get_divisors(x: int) -> list:
    divisors = []
    for i in range(1, x+1):
        if i * i > x:
            break
        if x % i == 0:
            divisors.append(i)
            if x // i != i:
                divisors.append(x // i)
    return divisors

N, M = li()
ans = 0
divs = get_divisors(M)
L = len(divs)


seni = [[] for _ in range(L)]
for i in range(L):
    for j in range(L):
        if M % (divs[i] * divs[j]) == 0:
            seni[i].append(j)
dp = [1] * L

for i in range(N-1):
    ndp = [0] * L
    for j in range(L):
        for k in seni[j]:
            ndp[k] += dp[j]
            ndp[k] %= mod
    dp = ndp

ans = 0
for i in range(L):
    ans += dp[i]
    ans %= mod

print(ans)
0