結果
問題 |
No.847 Divisors of Power
|
ユーザー |
![]() |
提出日時 | 2023-01-03 12:03:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 862 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 76,800 KB |
最終ジャッジ日時 | 2024-11-27 01:48:52 |
合計ジャッジ時間 | 2,577 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
def factorization(n): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) return arr def dfs(c, val): global ans if c == num: if val <= M: ans += 1 return for j in range(L[c]): now = val * A[c] ** j if now > M: return dfs(c + 1, now) return N, K, M = map(int, input().split()) L, A = [], [] val = 1 maxv = 1 for a, b in factorization(N): v, cnt = 1, 0 while v <= M: v *= a cnt += 1 cnt -= 1 L.append(min(b * K, cnt) + 1) A.append(a) val = min(b * K, cnt) num = len(A) ans = 0 dfs(0, 1) print(ans)