「BZOJ2793」[POI2012] Vouchers

2014年11月27日3,0240

Description

考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下的最小的x个。
正整数中有m个数被标成了幸运数,问有哪些人取到了幸运数。

Input

第一行一个正整数m (m<=1,000,000),下面m行每行一个正整数x (x<=1,000,000),表示x是一个幸运数。
接下来一行一个正整数n (n<=1,000,000),下面n行每行一个正整数x (x<=1,000,000),表示这一组来了x个人。

Output

第一行输出一个非负整数k,表示k个人取到了幸运数,下面k行依次表示取到幸运数的人的编号,人按照来的顺序从1开始编号。

Sample Input

4
1
6
8
16
3
4
2
4

Sample Output

3
2
4
6

HINT

Hint

总共来了10个人,他们取走的数依次是4 8 12 16 2 6 20 24 28 32。

第2、4、6个人取到的是幸运数8、16、6。
(别把这题想太难,其实很水的)

题解

一开始想错了真是逗。。。

其实就是只要考虑1-100w的数,然后mn[x]记录x的倍数取到了mn[x],下次取x的倍数就从mn[x]+x开始。。。

这复杂度是nlogn的貌似

 

avatar
  Subscribe  
提醒