結果
問題 |
No.1809 Divide NCK
|
ユーザー |
|
提出日時 | 2022-01-14 21:45:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 2,165 ms |
コンパイル使用メモリ | 201,832 KB |
最終ジャッジ日時 | 2025-01-27 11:12:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> map<T, T> divide(T n){//素因数分解 map<T, T> res; for(T i = 2; i * i <= n; i++){ while(n % i == 0){ res[i]++; n /= i; } } if(n != 1) res[n] = 1; return res; } int main(){ long long N, K, M; cin >> N >> K >> M; map<long long, long long> m = divide(M); map<long long, long long> cnt; for(auto [a, b] : m){ long long t = a; while(t <= N){ cnt[a] += N / t; if(t <= N / a) t *= a; else break; } t = a; while(t <= K){ cnt[a] -= K / t; if(t <= K / a) t *= a; else break; } t = a; while(t <= N - K){ cnt[a] -= (N - K) / t; if(t <= (N - K) / a) t *= a; else break; } } long long ans = N; for(auto [a, b] : m){ ans = min(ans, cnt[a] / b); } cout << ans << endl; }