[文章目录]
Description
考虑正整数集合，现在有n组人依次来取数，假设第i组来了x人，他们每个取的数一定是x的倍数，并且是还剩下的最小的x个。正整数中有m个数被标成了幸运数，问有哪些人取到了幸运数。n<=1000000,m<=1000000,x<=1000000
每个数的倍数个数和是nlnn的(调和级数)。
那么每次来x人，我们从上次来x人时扫到的位置继续扫，找下x个没有被标记的。总时间复杂度nlnn（POI的题好像都有些脑洞呢）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int lim=1000000;
ll ans[1001000];
int n,m;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
bool luck[1001000],vis[1001000];
int nxt[1001000];
int main()
{
read(m); int x;
while(m--)
{
read(x);
luck[x]=1;
}
read(n); ll id=0; int i,now,top=0;
while(n--)
{
read(x); now=nxt[x]+x;
for(i=1;i<=x;++i)
{
while(now<=lim&&vis[now]) now+=x;
if(now>lim) break;
vis[now]=1; if(luck[now]) ans[++top]=id+i;
}
nxt[x]=now; id+=x;
}
printf("%d\n",top);
for(int i=1;i<=top;++i) printf("%lld\n",ans[i]);
return 0;
}