题目描述

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

题目分析

因为幸运数最大10^6 那我们就枚举每个数在10^6内的倍数 看看那些没有取走
然后你T了
我们要加上点优化：记录某个数取到了哪个倍数 然后下次直接继续枚举即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,vis[1000010],can[1000010];
long long st[1000010],sum;
inline char get(void) 
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    if (p1 == p2) 
    {
        p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
        if (p1 == p2) return EOF;
    }
    return *p1++;
}
inline int read() 
{
    int x=0; static char c;
    for (; !(c >= '0' && c <= '9'); c = get());
    for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get());
    return x;
}
int last[1000010];
int main()
{   
    n=read();
    for(int x,i=1;i<=n;i++) x=read(),can[x]=1;
    m=read();
    for(int i=1;i<=1000000;i++) last[i]=i;
    for(int x,i=1;i<=m;i++)
    {
        x=read();
        int cnt=0;
        for(int j=last[x];j<=1000000;j+=x)
            if(!vis[j]) 
            {
                vis[j]=1,cnt++,sum++;
                last[x]=j;
                if(can[j]) st[++st[0]]=sum;
                if(cnt==x) break;
            }
        if(cnt!=x) sum=(long long) sum+x-cnt;
    }
    printf("%lld\n",st[0]);
    for(int i=1;i<=st[0];i++) printf("%lld\n",st[i]); 
    return 0;
}