与えられる合成数 $x$ 未満で、$x$ と共通の素因数が $K$ 個以上ある正整数のうち、約数が最も多いもの（候補が複数あるのならそれらの最小値）を求めてください。
・$4 \le x \le 100{,}000$
・$1 \le K \le 15$
・$x$ の素因数は $K$ 個より多いことは保証される
えらいハマってしまったわ。てへぺろー。
高度合成数のときみたいな感じで、必要な情報を持って探索。
・約数の個数
・共通の素因数の個数
・どの素数まで見て
・それを何個使ったか
・今の値
この辺が情報として存在していれば良い。
共通の素因数の個数は、事前に $x$ を素因数分解しておいて、
素数 $p$ の $k$ 個めを使おうとするときに $x$ の素因数 $p$ の個数と比較すれば、共通になるのか（一個増える）ならないのか（増えない）が分かる。
#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 = static_cast<Int>(sqrtl(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;
}
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()) {
auto [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;
}
(ΦωΦ)＜おしまい