結果
問題 | No.847 Divisors of Power |
ユーザー |
![]() |
提出日時 | 2019-07-05 22:25:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,376 bytes |
コンパイル時間 | 1,644 ms |
コンパイル使用メモリ | 183,016 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2024-10-06 22:19:17 |
合計ジャッジ時間 | 2,606 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; const int INF = 1 << 28; const ll MOD = 1000000007; template <class T> bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0; } template <class T> bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0; } template <typename T = ll> void primeFactors(T a, map<T, ll> &facs) { T origA = a; for (int i = 2; i * i <= origA; ++i) { while (a % i == 0) { facs[i]++; a /= i; } } if (a * a > origA) facs[a]++; return; } int main() { ll n, k, m; cin >> n >> k >> m; map<ll, ll> facs; primeFactors<ll>(n, facs); for (auto &p : facs) { p.second *= k; } set<ll> ret; set<ll> temp; ret.emplace(1); for (auto &p : facs) { temp.clear(); for (auto &r : ret) { temp.emplace(r); ll nextr = r; for (int i = 1; i <= p.second; ++i) { nextr *= p.first; if (nextr <= m) temp.emplace(nextr); else break; } } ret = temp; } cout << ret.size() << "\n"; return 0; }