結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2019-04-12 21:55:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 2,151 bytes |
コンパイル時間 | 1,963 ms |
コンパイル使用メモリ | 174,888 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 18:23:32 |
合計ジャッジ時間 | 2,585 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define lint long long#define P pair<int, int>#define LLP pair<long long, long long>#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)#define SORT(x) sort((x).begin(), (x).end())#define SORT_INV(x) sort((x).rbegin(), (x).rend())const int IINF = (1 << 30) - 1;const long long LLINF = 1LL << 61;const long long MOD = 1000000007LL;const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};const double EPS = 1e-8;bool comp(P &a, P &b){return a.second == b.second ? a.first < b.first : a.second > b.second;}int main(){cin.tie(0);ios::sync_with_stdio(false);int n, k;cin >> n >> k;vector< P > v;int m = n;for(int i = 2 ; i * i <= m ; ++i){if(m % i == 0){int cnt = 0;while(m % i == 0){m /= i;++cnt;}v.emplace_back(i, cnt);}}if(m > 1){v.emplace_back(m, 1);}int siz = v.size();vector< P > t;REP(i, 2, n){int now = i, cnt = 0;rep(j, siz){if(v[j].first > now){break;}int tmp = 0;while(now % v[j].first == 0 && tmp < v[j].second){now /= v[j].first;++tmp;}cnt += tmp;}if(cnt < k){continue;}cnt = 0;for(int j = 1 ; j * j <= i ; ++j){if(i % j == 0){if(j * j == i){++cnt;}else{cnt += 2;}}}t.emplace_back(i, cnt);}sort(t.begin(), t.end(), comp);cout << t[0].first << endl;return 0;}