#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define sz(s) (int)s.size()
#define bit(i, j) ((j >> i) & 1)
#define all(v) v.begin(), v.end()
#define taskname "file"
typedef long long ll;
const int N = 1e7, M = 1e5;
int m, q, p[N + 5], dp[N + 5], u[N + 5];
bool cnt[N + 5];
void sangnt(){
vector <int> v;
for (int i = 2; i <= N; ++i){
if (!u[i]){
u[i] = i;
v.push_back(i);
}
for (int j : v){
if (i * j > N) break;
u[i * j] = j;
if (u[i * j] == u[i]) break;
}
}
}
void solve(){
sangnt();
cin >> m >> q;
for (int i = 1; i <= m; ++i){
cin >> p[i];
cnt[p[i]] = true;
}
dp[0] = 0;
deque <int> dq;
dq.push_back(0);
int pos = 1;
while (pos <= N){
int mx = -1;
while (sz(dq)){
int x = dq.back();
dq.pop_back();
if (!x){
for (int i = 1; i <= m; ++i) mx = max(mx, p[i] - 1);
}
else{
int d = x;
while (d > 1){
int uoc = u[d];
if (!cnt[uoc]) break;
mx = max(mx, x + uoc - 1);
d /= uoc;
}
}
}
if (pos > mx) break;
if (mx > N) mx = N;
for (int i = pos; i <= mx; ++i){
dq.push_back(i);
dp[i] = dp[pos - 1] + 1;
}
pos = mx + 1;
}
while (q--){
int n;
cin >> n;
if (!n) cout << 0 << "\n";
else if (dp[n]) cout << dp[n] << "\n";
else cout << "oo\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen(taskname".inp", "r", stdin);
// freopen(taskname".out", "w", stdout);
int tt = 1;
// cin >> tt;
while (tt--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |