Description 考慮正整數集合，現在有n組人依次來取數，假設第i組來了x人，他們每個取的數一定是x的倍數，並且是還剩下的最小的x個。正整數中有m個數被標成了幸運數，問有哪些人取到了幸運數。 考慮正整數集合，現在有n組人依次來取數，假設第i組來了x人，他們每個取的數一定是x的倍數，並且是還剩下 ...
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
41
6
8
16
3
4
2
4
Sample Output
32
4
6
HINT
Hint
總共來了10個人，他們取走的數依次是4 8 12 16 2 6 20 24 28 32。
第2、4、6個人取到的是幸運數8、16、6。
（別把這題想太難，其實很水的）
Source
我真傻，真的。 單知道這題是個大暴力就不用花半個小時去推式子。。。 還是太菜了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; }
