結果
問題 | No.1809 Divide NCK |
ユーザー |
![]() |
提出日時 | 2022-01-14 21:44:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 1,234 bytes |
コンパイル時間 | 1,082 ms |
コンパイル使用メモリ | 84,716 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-20 09:06:15 |
合計ジャッジ時間 | 2,637 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <iostream> #include <vector> #include <map> using namespace std; typedef long long ll; typedef pair<ll, ll> P; const ll INF = 1000000000000000000; std::vector<int> enum_prime(int n){ // containing n std::vector<int> res; if (n <= 1) return res; std::vector<bool> p(n + 1); fill(p.begin() + 2, p.end(), true); for(int i = 2; i <= n; i++){ if(p[i]){ res.push_back(i); for(int j = i * 2; j <= n; j += i) p[j] = false; } } return res; } int main() { ll n, k, m; cin >> n >> k >> m; vector<int> prime = enum_prime(1000000); map<ll, ll> mp; for(ll p : prime){ if(m % p == 0){ while(m % p == 0){ mp[p]++; m /= p; } } } if(m > 1) mp[m] = 1; ll ans = INF; for(P q : mp){ ll p = q.first; ll c = 0; ll t; t = n; while(t){ t /= p; c += t; } t = k; while(t){ t /= p; c -= t; } t = n - k; while(t){ t /= p; c -= t; } ans = min(ans, c / q.second); } cout << ans << endl; }