【BZOJ2793】[Poi2012]Vouchers
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
1
6
8
16
3
4
2
4
Sample Output
3
2
4
6
2
4
6
HINT
Hint
总共来了10个人，他们取走的数依次是4 8 12 16 2 6 20 24 28 32。
第2、4、6个人取到的是幸运数8、16、6。
题解：水题，对于所有可能的x，维护一下x的最后一个人取到了哪个数，然后暴力即可。根据调和级数，这样做的复杂度是O(n ln n)的。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n,m,mx;
ll sum;
int vis[maxn],lk[maxn],last[maxn];
ll ans[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
m=rd();
int i,j,a,b;
for(i=1;i<=m;i++) a=rd(),mx=max(mx,a),lk[a]=1;
n=rd();
for(i=1;i<=n;i++)
{
a=rd(),b=0;
for(j=last[a]+a;j<=mx&&b<a;last[a]=j,j+=a)
{
if(!vis[j])
{
b++,vis[j]=1;
if(lk[j]) ans[++ans[0]]=sum+b;
}
}
sum+=a;
}
for(i=0;i<=ans[0];i++) printf("%lld\n",ans[i]);
return 0;
}