結果

問題 No.1973 Divisor Sequence
ユーザー EguyEguy
提出日時 2022-06-10 22:13:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 894 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 81,684 KB
実行使用メモリ 80,028 KB
最終ジャッジ日時 2023-10-21 05:19:11
合計ジャッジ時間 6,951 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,632 KB
testcase_01 AC 39 ms
53,588 KB
testcase_02 AC 439 ms
75,600 KB
testcase_03 AC 64 ms
70,608 KB
testcase_04 AC 276 ms
75,600 KB
testcase_05 AC 84 ms
75,600 KB
testcase_06 AC 182 ms
75,588 KB
testcase_07 AC 84 ms
75,592 KB
testcase_08 AC 131 ms
75,592 KB
testcase_09 AC 247 ms
75,600 KB
testcase_10 AC 924 ms
75,624 KB
testcase_11 AC 89 ms
75,592 KB
testcase_12 AC 165 ms
75,588 KB
testcase_13 AC 106 ms
75,592 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