#include <bits/stdc++.h>
using namespace std;
#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;
int pos = 0, mx = 0;
while (pos <= N){
int gh = -1;
for (int i = pos; i <= mx; ++i){
int x = i;
if (!x){
for (int i = 1; i <= m; ++i) gh = max(gh, p[i] - 1);
}
else{
int d = x;
while (d > 1){
int uoc = u[d];
if (!cnt[uoc]) break;
gh = max(gh, x + uoc - 1);
d /= uoc;
}
}
}
if (pos > gh) break;
if (gh > N) gh = N;
for (int i = mx + 1; i <= gh; ++i)
dp[i] = dp[pos] + 1;
pos = mx + 1;
mx = gh;
}
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... |