結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2019-04-12 21:35:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 1,661 bytes |
コンパイル時間 | 1,267 ms |
コンパイル使用メモリ | 116,240 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 17:30:26 |
合計ジャッジ時間 | 2,522 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
/* ---------- STL Libraries ---------- */ // IO library #include <cstdio> #include <fstream> #include <iomanip> #include <ios> #include <iostream> // algorithm library #include <algorithm> #include <cmath> #include <numeric> #include <random> #include <cstring> // container library #include <array> #include <bitset> #include <deque> #include <map> #include <unordered_map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> #include <stack> /* ---------- Namespace ---------- */ using namespace std; /* ---------- Type ---------- */ using ll = long long; #define int ll #define P pair<ll, ll> /* ---------- Constants */ const double PI = 3.141592653589793238462643383279; const ll MOD = 1e9 + 7; const int INF = 1LL << 55; map<int, int> prime_factor(int n) { map<int, int> ret; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { ret[i]++; n /= i; } } if (n != 1) ret[n] = 1; return move(ret); }; signed main() { int N, K; cin >> N >> K; map<int, int> n_factors = prime_factor(N); int mx = -1; int ret = -1; for (int i = 1; i < N; i++) { map<int, int> i_factors = prime_factor(i); int common_factor_n = 0; int div_n = 1; for (auto it = i_factors.begin(); it != i_factors.end(); it++) { common_factor_n += min(it->second, n_factors[it->first]); div_n *= 1 + it->second; } if (common_factor_n >= K) { if (div_n > mx) { mx = div_n; ret = i; } } } cout << ret << endl; return 0; }