結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2019-04-12 22:03:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,612 bytes |
コンパイル時間 | 1,864 ms |
コンパイル使用メモリ | 171,104 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 18:49:45 |
合計ジャッジ時間 | 2,585 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lli = int_fast64_t;using ulli = uint_fast64_t;#define debug(x) cerr << #x << " : " << x << endl#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endltemplate<typename T>T ncr(T left, T right) {right = min(left - right, right);T ans = 1;for (T i = 1; i <= right; i++) {ans = ans * (left - right + i) / i;}return ans;}const lli MOD = 1000000007;const lli LIMIT = 1000000000000000000 * 5;const int tenfive = 100000;int main() {int N, K;vector<int> v;cin >> N >> K;int sub = N;for (int i = 2; i <= sub; i++) {if (sub % i == 0) {v.push_back(i);sub /= i;i--;}}int save = 1;int ans = 1;vector<bool> table(N, false);for (int i = 1; i < pow(2, v.size()) - 1; i++) {bitset<20> b(i);if (b.count() < K)continue;int num = 1;for (int j = 0; j < v.size(); j++) {if (b[j]) {num *= v[j];}}for (int k = 1; k*num < N; k++) {int p = 0;int snum = k * num;if (table[snum])continue;table[snum] = true;for (int j = 1; j*j <= snum; j++) {if (snum%j == 0) {p += 2;if (j*j == snum)p--;}}if (save < p || (save == p && ans > snum)) {save = p;ans = snum;}}}cout << ans << endl;return 0;}