<div class="post_brief"><p>
决心写一道usaco之外的题，于是就挑中了这道。</p>

 

为啥这编辑器有BUG，每次按回车要向下跳？

 

发现可以预处理DP。f_i表示第i个数被砍完需要最少多少刀。对于每一个i，设p_i是它的质因子里最大的一个在给定集合里的，那么它可以转移到(i+1,i+p_i)这个范围。然后f_i显然不减，所以用单调队列之类的玩意。

 

然后卡着时间限制过了。不知道前面那些秒跑的人是怎么搞的。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int maxn = 10000009;
const int maxm = 100009;


int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm];


void pre(int n) {
sort(p, p + m);
memset(k, 0, sizeof(k));
for (int i = 0; i < m; ++ i)
if (!i || p[i] != p[i - 1])
for (int j = 0; j <= n; j += p[i])
k[j] = p[i];


static int q[maxn];
int hd(0), tl(1);
q[0] = f[0] = 0;
for (int i = 1; i &lt;= n; ++ i) {
	while (hd &lt; tl &amp;&amp; i &gt;= q[hd] + k[q[hd]])
		++ hd;
	if (hd == tl) {
		f[i] = -1;
		continue;
	}
	f[i] = f[q[hd]] + 1;
	while (hd &lt; tl &amp;&amp; (f[i] &lt; f[q[tl - 1]] || (f[i] == f[q[tl - 1]] &amp;&amp; i + k[i] &gt;= q[tl - 1] + k[q[tl - 1]])))
		-- tl;
	q[tl ++] = i;
}



}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d%d", &amp;m, &amp;q);
memset(k, 0, sizeof(k));
for (int i = 0; i &lt; m; ++ i)
	scanf("%d", p + i);
n = 0;
for (int i = 0; i &lt; q; ++ i) {
	scanf("%d", v + i);
	if (v[i] &gt; n)
		n = v[i];
}
pre(n);
for (int i = 0; i &lt; q; ++ i)
	if (f[v[i]] == -1)
		puts("oo");
	else
		printf("%d\n", f[v[i]]);



}