結果

問題 No.1973 Divisor Sequence
ユーザー EguyEguy
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
60,028 KB
testcase_01 AC 38 ms
52,544 KB
testcase_02 AC 427 ms
76,268 KB
testcase_03 AC 63 ms
70,064 KB
testcase_04 AC 276 ms
76,332 KB
testcase_05 AC 83 ms
76,196 KB
testcase_06 AC 181 ms
76,012 KB
testcase_07 AC 84 ms
76,028 KB
testcase_08 AC 131 ms
76,248 KB
testcase_09 AC 246 ms
76,204 KB
testcase_10 AC 926 ms
75,932 KB
testcase_11 AC 90 ms
76,124 KB
testcase_12 AC 166 ms
76,044 KB
testcase_13 AC 104 ms
75,996 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

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