結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2019-04-13 13:12:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,166 ms / 2,000 ms |
コード長 | 877 bytes |
コンパイル時間 | 1,561 ms |
コンパイル使用メモリ | 173,760 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 08:43:33 |
合計ジャッジ時間 | 7,385 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { auto is_prime = [](int x) { if (x == 2) { return true; } for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; }; int n, k; cin >> n >> k; map<int, int> mp; for (int i = 2, j = n; j != 1; i++) { while (j % i == 0) { mp[i]++; j /= i; } } int num = 0, ans = 0; for (int i = 2; i < n; i++) { map<int, int> tmp; if (is_prime(i)) { tmp[i] = 1; } else { for (int j = i, l = 2; j != 1; l++) { while (j % l == 0) { tmp[l]++; j /= l; } } } int puni = 0, muni = 1; for (auto &p : tmp) { muni *= (p.second + 1); } for (auto &p : mp) { puni += min(p.second, tmp[p.first]); } if (k <= puni && num < muni) { num = muni; ans = i; } } cout << ans << endl; return 0; }