BZOJ 2793: [Poi2012]Vouchers(调和级数)

2018-02-28 07:45:40来源:cnblogs.com作者:自为风月马前卒人点击

分享
第七城市
Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 582  Solved: 250
[Submit][Status][Discuss]

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。


(别把这题想太难,其实很水的)


Source

鸣谢Oimaster

 我真傻,真的。单知道这题是个大暴力就不用花半个小时去推式子。。。还是太菜了QWQ.... 我们用$have[x]$表示$x$的倍数已经枚举到了多少然后对于每个询问暴力枚举就可以了。。起点是$have[x]+x$时间复杂度$/dfrac {n}{1}+/dfrac {n}{2}+/ldots +/dfrac {n}{n}=n/log n$  
// luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#define int long long //#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)//char BB[1 << 15], *S = BB, *T = BB;using namespace std;const int MAXN=1e6+10;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int have[MAXN],take[MAXN],a[MAXN],limit=0;int ans[MAXN],cnt=0;main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    int N=read();    for(int i=1;i<=N;i++)     {        int x=read();        limit=max(limit,x);        a[x]=1;    }    int M=read();    int now=0;    while(M--)    {        int x=read(),t=x;        for(int i=have[x]+x;i<=limit;i+=x)        {            if(!take[i])            {                now++;t--;                take[i]=1;                if(a[i]) ans[++cnt]=now;            }            have[x]=i;            if(t==0) break;        }        now+=t;    }    printf("%lld/n",cnt);    for(int i=1;i<=cnt;i++)        printf("%lld/n",ans[i]);    return 0;}
第七城市

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台