結果

問題 No.811 約数の個数の最大化
ユーザー ldsybldsyb
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0