#include <iostream>
#include <queue>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#if 1
#define M 100005
#define N 10000005
#else
#define M 20000
#define N 20000
#endif
int m, q, dp[N], yes[N], freq[N];
priority_queue<int, vector<int>, greater<int>> pq;
int si[4000];
vector<int> prime;
struct Precalc {
unsigned char divisor[1<<16];
constexpr Precalc() : divisor{} {
for (int i = 0; i < (1<<16); i++)
divisor[i] = 1;
for (int i = 2; i * i < (1<<16); i++)
if (divisor[i] == 1)
for (int k = i * i; k < (1<<16); k += i)
divisor[k] = i;
}
};
int main()
{
for (int i = 2; i < 4000; ++i)
{
if (si[i]) continue;
for (int j = 2 * i; j < 4000; j += i) si[j] = 1;
}
for (int i = 2; i < 4000; ++i) if (!si[i]) prime.push_back(i);
memset(dp, 63, sizeof dp);
ShinLena;
dp[0] = 0;
cin >> m >> q;
for (int p, i = 1; i <= m; ++i)
{
cin >> p;
yes[p] = 1;
}
constexpr Precalc P{};
auto factorize2 = [&](int n) {
vector<int> f;
using u64 = unsigned long long;
auto find_factor = [&](u64 n){
if (n < (1 << 16)) return u64(P.divisor[n]);
for (u64 d : prime)
if (d * n < d)
return u64(-1) / d + 1;
return 1ull;
};
u64 d;
do {
f.push_back(d = find_factor(n));
n /= d;
} while (d != 1);
return f;
};
for (int i = 1; i < N; ++i) volatile auto F = factorize2(i);
return 0;
auto push = [&](int x){
pq.push(x);
};
auto del = [&](int x){
++freq[x];
};
auto top = [&](){
while (pq.size())
{
int top = pq.top();
if (freq[top]) --freq[top], pq.pop();
else return top;
}
return int(1e9);
};
for (int i = 0; i < m; ++i) push(0);
for (int i = 1; i < N; ++i)
{
auto F = factorize(i);
for (auto x : F) if (yes[x] and dp[i-x] < N)
del(dp[i-x]);
dp[i] = min(dp[i], top() + 1);
if (dp[i] < 1e9)
for (auto x : F) if (yes[x])
push(dp[i]);
}
for (int x, i = 1; i <= q; ++i)
{
cin >> x;
if (dp[x] >= 1e9) cout << "oo\n";
else cout << dp[x] << '\n';
}
return 0;
}
Compilation message
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:124:18: error: 'factorize' was not declared in this scope; did you mean 'factorize2'?
124 | auto F = factorize(i);
| ^~~~~~~~~
| factorize2
