結果
問題 | No.811 約数の個数の最大化 |
ユーザー | yuppe19 😺 |
提出日時 | 2019-04-12 23:17:59 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,091 bytes |
コンパイル時間 | 913 ms |
コンパイル使用メモリ | 91,208 KB |
実行使用メモリ | 5,080 KB |
最終ジャッジ日時 | 2023-10-13 09:10:03 |
合計ジャッジ時間 | 1,976 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 6 ms
4,972 KB |
testcase_03 | AC | 2 ms
4,356 KB |
testcase_04 | AC | 1 ms
4,352 KB |
testcase_05 | AC | 1 ms
4,352 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,352 KB |
testcase_08 | AC | 4 ms
4,352 KB |
testcase_09 | AC | 4 ms
4,352 KB |
testcase_10 | AC | 3 ms
4,352 KB |
testcase_11 | AC | 6 ms
4,952 KB |
testcase_12 | AC | 2 ms
4,352 KB |
testcase_13 | AC | 6 ms
5,080 KB |
testcase_14 | AC | 6 ms
5,044 KB |
ソースコード
#include <cassert> #include <cmath> #include <iostream> #include <tuple> #include <queue> #include <vector> using namespace std; using i64 = int64_t; vector<int> factorize(int n) { vector<int> v(n+1); for(int d=2; d*d<=n; ++d) { while(n % d == 0) { ++v[d]; n /= d; } } if(n > 1) { ++v[n]; } return v; } template <class Int> vector<Int> sieve(Int n) { vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false; Int sq = Int(sqrt(n)); for(Int i=2; i<=sq; ++i) { if(is_prime[i]) { for(Int j=i*i; j<=n; j+=i) { is_prime[j] = false; } } } vector<Int> res; for(Int i=2; i<=n; ++i) { if(is_prime[i]) { res.push_back(i); } } return res; } void debug(const vector<int> &vec_) { for(size_t i=0, n=vec_.size(); i<n; ++i) { if(i) { fprintf(stderr, " "); } fprintf(stderr, "%d", vec_[i]); } fprintf(stderr, "\n"); } i64 f(int x, int K) { constexpr int inf = 987'654'321; vector<int> primes = sieve(x); int n = static_cast<int>(primes.size()); vector<int> fac = factorize(x); // 約数の個数(dcnt), 共通の素因数の個数(ccnt), i番目の素数, k個使う, 値 queue<tuple<int, int, int, int, i64>> que; que.emplace(1, 0, 0, 0, 1); i64 res = inf; int max_dcnt = 0; while(!que.empty()) { int dcnt, ccnt, i, k; i64 val; tie(dcnt, ccnt, i, k, val) = que.front(); que.pop(); if(val >= x) { continue; } if(ccnt >= K) { if(max_dcnt < dcnt) { max_dcnt = dcnt; res = val; } else if(max_dcnt == dcnt) { res = min(res, val); } } // i番目をk個からk+1個にする int p = primes[i]; bool have = fac[p] >= k+1; que.emplace(dcnt*(k+2)/(k+1), ccnt+have, i, k+1, val*p); // j番目をはじめて使う for(int j=i+1; j<n && val*primes[j]<x; ++j) { p = primes[j]; have = fac[p] >= 1; que.emplace(dcnt*2, ccnt+have, j, 1, val*p); } } return res; } int main(void) { int N, K; scanf("%d%d", &N, &K); i64 res = f(N, K); printf("%ld\n", res); return 0; }