結果
問題 |
No.473 和と積の和
|
ユーザー |
|
提出日時 | 2016-11-17 18:28:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,116 bytes |
コンパイル時間 | 335 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 664,200 KB |
最終ジャッジ日時 | 2024-12-16 02:20:57 |
合計ジャッジ時間 | 22,549 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 TLE * 1 MLE * 3 |
ソースコード
def divisors(N): ret = [] d = 1 while d * d <= N: if N % d == 0: ret.append(d) if(d * d != N): ret.append(N / d) d += 1 ret.sort() return ret N, X = map(int, input().split()) D = divisors(X + 1) M = {} for i, d in enumerate(D): M[d] = i dp = [[[-1 for i in range(32)] for j in range(len(D))] for j in range(len(D))] def dec(n, m, k): if k >= 32: return 0 if dp[n][m][k] >= 0: return dp[n][m][k] if k == 0: if D[n] == 1: dp[n][m][k] = 1 return 1 else: dp[n][m][k] = 0 return 0 if k == 1: if n >= m: dp[n][m][k] = 1 return 1 else: dp[n][m][k] = 0 return 0 ret = 0 p = m while D[p] * D[p] <= D[n]: if D[n] % D[p] == 0: a = D[n] cnt = 1 while a % D[p] == 0 and k >= cnt: a /= D[p] ret += dec(M[a], p + 1, k - cnt) cnt += 1 p += 1 dp[n][m][k] = ret return ret print(dec(len(D) - 1, 1, N))