結果
問題 |
No.1809 Divide NCK
|
ユーザー |
![]() |
提出日時 | 2022-01-14 22:19:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,077 bytes |
コンパイル時間 | 1,756 ms |
コンパイル使用メモリ | 173,136 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-20 11:33:21 |
合計ジャッジ時間 | 2,849 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 15 |
ソースコード
#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_fast64_t,int>prime_factor(int_fast64_t x){ map<int_fast64_t,int>res; for(int_fast64_t 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=pow(it.first,it.second); 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); } cout<<ans<<endl; return 0; }