#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int mx = 1e7+5;
const int maxn = 1e5+5;
typedef long long ll;
ll lim = 1;
int m, q, ans;
int dp[mx], cnt[mx], pp[mx], mm[mx];
vector<int> primes;
int l = 0, r = 0;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> q;
for(int i = 2; i < mx; i++){
if(!pp[i]){
pp[i]=i;
primes.push_back(i);
}
for(auto v: primes){
if(i*v >= mx)break;
pp[i*v]=v;
if(i%v==0)break;
}
}
while(m--){
int x;
cin >> x;
if(!mm[x]){
lim*=x;
if(lim >= mx)lim = mx;
cnt[0]++;
}
mm[x] = 1;
}
for(int i = 1; i < lim; i++){
int tmp = i;
while(pp[tmp]){
int prv = pp[tmp];
while(pp[tmp] == prv){
tmp/=prv;
}
if(mm[prv]){
cnt[i-prv]--;
cnt[i]++;
}
}
while(!cnt[r])r++;
dp[i]=dp[r]+1;
}
while(q--){
int x;
cin >> x;
if(x >= lim)cout << "oo";
else cout << dp[x];
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
43632 KB |
Output is correct |
2 |
Correct |
648 ms |
120636 KB |
Output is correct |
3 |
Correct |
130 ms |
44256 KB |
Output is correct |
4 |
Correct |
760 ms |
120472 KB |
Output is correct |
5 |
Correct |
579 ms |
120472 KB |
Output is correct |
6 |
Correct |
125 ms |
43676 KB |
Output is correct |
7 |
Correct |
178 ms |
44276 KB |
Output is correct |
8 |
Correct |
150 ms |
49244 KB |
Output is correct |
9 |
Correct |
624 ms |
120544 KB |
Output is correct |
10 |
Correct |
613 ms |
120660 KB |
Output is correct |
11 |
Correct |
592 ms |
120516 KB |
Output is correct |
12 |
Correct |
712 ms |
120540 KB |
Output is correct |
13 |
Correct |
708 ms |
120588 KB |
Output is correct |
14 |
Correct |
708 ms |
120556 KB |
Output is correct |
15 |
Correct |
609 ms |
120508 KB |
Output is correct |
16 |
Correct |
645 ms |
120592 KB |
Output is correct |
17 |
Correct |
615 ms |
120524 KB |
Output is correct |
18 |
Correct |
618 ms |
120544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
655 ms |
124040 KB |
Output is correct |
2 |
Correct |
689 ms |
155656 KB |
Output is correct |
3 |
Correct |
738 ms |
124452 KB |
Output is correct |
4 |
Correct |
661 ms |
120820 KB |
Output is correct |
5 |
Correct |
783 ms |
125644 KB |
Output is correct |
6 |
Correct |
611 ms |
120736 KB |
Output is correct |
7 |
Correct |
668 ms |
124040 KB |
Output is correct |
8 |
Correct |
611 ms |
120648 KB |
Output is correct |
9 |
Correct |
765 ms |
125696 KB |
Output is correct |
10 |
Correct |
697 ms |
124436 KB |
Output is correct |
11 |
Correct |
703 ms |
122416 KB |
Output is correct |
12 |
Correct |
667 ms |
120720 KB |
Output is correct |
13 |
Correct |
600 ms |
122424 KB |
Output is correct |
14 |
Correct |
649 ms |
120848 KB |
Output is correct |
15 |
Correct |
756 ms |
123640 KB |
Output is correct |
16 |
Correct |
662 ms |
155720 KB |
Output is correct |
17 |
Correct |
684 ms |
120736 KB |
Output is correct |
18 |
Correct |
780 ms |
128568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
767 ms |
124612 KB |
Output is correct |
2 |
Correct |
699 ms |
123312 KB |
Output is correct |
3 |
Correct |
689 ms |
123180 KB |
Output is correct |
4 |
Correct |
703 ms |
121104 KB |
Output is correct |
5 |
Correct |
702 ms |
137976 KB |
Output is correct |
6 |
Correct |
758 ms |
121372 KB |
Output is correct |
7 |
Correct |
762 ms |
129680 KB |
Output is correct |
8 |
Correct |
796 ms |
124512 KB |
Output is correct |
9 |
Correct |
800 ms |
124480 KB |
Output is correct |
10 |
Correct |
743 ms |
120932 KB |
Output is correct |
11 |
Correct |
720 ms |
120928 KB |
Output is correct |
12 |
Correct |
768 ms |
120984 KB |
Output is correct |
13 |
Correct |
789 ms |
122268 KB |
Output is correct |
14 |
Correct |
663 ms |
121048 KB |
Output is correct |
15 |
Correct |
768 ms |
120960 KB |
Output is correct |
16 |
Correct |
746 ms |
120884 KB |
Output is correct |
17 |
Correct |
793 ms |
123676 KB |
Output is correct |
18 |
Correct |
766 ms |
123312 KB |
Output is correct |
19 |
Correct |
722 ms |
123256 KB |
Output is correct |
20 |
Correct |
883 ms |
123232 KB |
Output is correct |
21 |
Correct |
704 ms |
121100 KB |
Output is correct |
22 |
Correct |
834 ms |
126572 KB |
Output is correct |
23 |
Correct |
853 ms |
124632 KB |
Output is correct |
24 |
Correct |
789 ms |
121148 KB |
Output is correct |
25 |
Correct |
833 ms |
120980 KB |
Output is correct |
26 |
Correct |
864 ms |
121172 KB |
Output is correct |
27 |
Correct |
774 ms |
125620 KB |
Output is correct |
28 |
Correct |
659 ms |
121192 KB |
Output is correct |
29 |
Correct |
911 ms |
126508 KB |
Output is correct |
30 |
Correct |
870 ms |
124616 KB |
Output is correct |
31 |
Correct |
760 ms |
121864 KB |
Output is correct |
32 |
Correct |
848 ms |
121112 KB |
Output is correct |
33 |
Correct |
656 ms |
121500 KB |
Output is correct |
34 |
Correct |
959 ms |
129652 KB |
Output is correct |
35 |
Correct |
687 ms |
121128 KB |
Output is correct |
36 |
Correct |
872 ms |
126500 KB |
Output is correct |
37 |
Correct |
766 ms |
137996 KB |
Output is correct |
38 |
Correct |
865 ms |
121304 KB |
Output is correct |
39 |
Correct |
757 ms |
121304 KB |
Output is correct |
40 |
Correct |
897 ms |
121540 KB |
Output is correct |
41 |
Correct |
928 ms |
133456 KB |
Output is correct |
42 |
Correct |
785 ms |
120948 KB |
Output is correct |