結果
問題 | No.1809 Divide NCK |
ユーザー |
![]() |
提出日時 | 2022-01-14 22:27:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,036 bytes |
コンパイル時間 | 1,910 ms |
コンパイル使用メモリ | 174,224 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-20 12:00:31 |
合計ジャッジ時間 | 3,024 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; using pii=pair<int,int>; #define INF LONG_MAX #define MOD1 1000000007 #define MOD2 998244353 #define MOD MOD1 #define rng(a) a.begin(),a.end() #define rrng(a) a.end(),a.begin() #define endl "\n" #define int ll map<int,int>prime_factor(int x){ map<int,int>res; for(int i=2;i*i<=x;i++){ while(x%i==0){ res[i]++; x/=i; } } if(x!=1)res[x]=1; return res; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int N,K,M; cin>>N>>K>>M; auto p=prime_factor(M); int ans=LONG_LONG_MAX; for(auto it:p){ int res=0; int m=it.first; int d=1; while(true){ int nd=N/d; int nkd=(N-K)/d; int kd=K/d; res+=nd-nkd-kd; if(d>N/m){ break; } d*=m; } ans=min(ans,res/it.second); } cout<<ans<<endl; return 0; }