結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
|
提出日時 | 2019-04-12 23:17:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,091 bytes |
コンパイル時間 | 1,128 ms |
コンパイル使用メモリ | 94,452 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 06:17:55 |
合計ジャッジ時間 | 1,806 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#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; }