結果
問題 | 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;}