結果
問題 |
No.847 Divisors of Power
|
ユーザー |
![]() |
提出日時 | 2019-07-08 12:51:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 988 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 76,560 KB |
最終ジャッジ日時 | 2024-10-07 01:23:14 |
合計ジャッジ時間 | 2,847 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
def factoring(n): i = 2 fact = [] while True: if n < i * i: break if n % i == 0: fact.append(i) n //= i else: i += 1 fact.append(n) t = fact[0] fact_converted = [] cnt = 0 for x in fact: if t == x: cnt += 1 else: fact_converted.append([t, cnt]) t = x cnt = 1 fact_converted.append([t, cnt]) return fact_converted def count(mass, fact, k, M, leng): if mass > M: return 0 if k == leng: return 1 cnt = 0 for i in range(fact[k][1] + 1): sum = count(mass * (fact[k][0] ** i), fact, k + 1, M, leng) if sum == 0: break else: cnt += sum return cnt N, K, M = map(int, input().split()) if N == 1: print('1') else: fact = [[x[0], x[1] * K] for x in factoring(N)] leng = len(fact) print(count(1, fact, 0, M, leng))