結果
問題 | No.811 約数の個数の最大化 |
ユーザー | sinsincoscos |
提出日時 | 2019-04-12 23:18:02 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 772 ms |
コンパイル使用メモリ | 80,092 KB |
実行使用メモリ | 4,356 KB |
最終ジャッジ日時 | 2023-10-13 09:10:16 |
合計ジャッジ時間 | 1,807 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | AC | 40 ms
4,352 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 4 ms
4,348 KB |
testcase_07 | AC | 5 ms
4,348 KB |
testcase_08 | AC | 19 ms
4,348 KB |
testcase_09 | AC | 20 ms
4,348 KB |
testcase_10 | AC | 14 ms
4,356 KB |
testcase_11 | AC | 38 ms
4,348 KB |
testcase_12 | AC | 10 ms
4,348 KB |
testcase_13 | AC | 43 ms
4,348 KB |
testcase_14 | AC | 44 ms
4,352 KB |
ソースコード
#include <iostream> #include <map> #include <vector> using namespace std; typedef pair<int,int> P; int N,K; map<int,int> m; int main(){ cin >> N >> K; int n = N; for(int i=2;i*i<=N;i++){ while(n%i==0){ n /= i; m[i]++; } } if(n!=1) m[n]++; int ans = 1e9,ma = 0; for(int i=2;i<N;i++){ int n2 = i; map<int,int> m2; for(int j=2;j*j<=n2;j++){ while(n2%j==0){ n2 /= j; m2[j]++; } } if(n2!=1) m2[n2]++; int num = 1,cnt = 0; for(auto x:m2){ num *= x.second+1; if(m.count(x.first)) cnt += min(m[x.first],x.second); } //cerr << i << " " << num << " " << cnt << endl; if(cnt<K) continue; if(ma<num) ans = i; if(ma==num) ans = min(ans,i); ma = max(ma,num); } cout << ans << endl; }