結果
問題 | No.847 Divisors of Power |
ユーザー |
|
提出日時 | 2019-07-05 21:50:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 1,783 ms |
コンパイル使用メモリ | 175,688 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 21:28:05 |
合計ジャッジ時間 | 2,675 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; map<int64_t, int64_t> prime_division(int64_t n){ map<int64_t, int64_t> ret; for(int64_t i=2; i*i<=n; i++){ while(n % i == 0){ n /= i; ret[i]++; } } if(n > 1) ret[n] = 1; return ret; } int main(){ int64_t N, K, M; cin >> N >> K >> M; auto primes = prime_division(N); vector<int> dp = {1}; for(auto& pr : primes){ int p = pr.first; int64_t mx = pr.second * K; vector<int> dp2; for(int64_t a : dp){ for(int t=0; t<mx; t++){ a *= p; if(a > M) break; dp2.push_back(a); } } for(int a : dp2) dp.push_back(a); } cout << dp.size() << endl; return 0; }