結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2019-04-12 21:58:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,611 bytes |
コンパイル時間 | 1,622 ms |
コンパイル使用メモリ | 173,396 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-14 18:35:10 |
合計ジャッジ時間 | 2,573 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 WA * 1 |
ソースコード
#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 << endl template<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--; } } debugv(v); 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; debug(snum); 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; } } } cout << ans << endl; return 0; }