ZUFE2486 Heap

2486: Heap

题目描述

有n个非负整数，a1,a2,a3.....an。

有Q次询问，每次询问输入四个正整数A,B,C,D

每次询问输出有多少个ai，满足ai%A==0 && ai%B==0 && ai%C==0 && ai%D==0。

输入

第一行输入T，表示有T组测试数据。

每组测试数据，

第一行输入n，

第二行输入n个非负整数，

第三行输入Q，

接下来Q行每行输入四个正整数A,B,C,D。

1<=n<=100000

0<=ai<=100000

1<=Q<=100000

1<=A,B,C,D<=10000

输出

每次询问，输出满足条件的数字个数。

样例输入

1 5 1 2 3 4 5 3 1 1 1 1 1 1 2 2 1 2 3 4

样例输出

5 2 0

提示

来源

周甄陶

————————————————————————————————————————

首先感谢学长的命题与指导！

思路：因为a不大，所以一旦4个数的LCM大于1e5的话答案就是0的个数，否则预处理统计下每个数的倍数有多少个即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <cmath>

using namespace std;

#define LL long long

const int INF=0x3f3f3f3f;

int cnt[100005],a[100005];

LL gcd(LL x,LL y)

{

return x%y==0?y:gcd(y,x%y);

}

int main()

{

int T;

LL a1,a2;

int x,n,q;

scanf("%d",&T);

while(T--)

{

scanf("%d",&n);

memset(cnt,0,sizeof cnt);

memset(a,0,sizeof a);

for(int i=0; i<n; i++)

scanf("%d",&x),cnt[x]++;

for(int i=1; i<100005; i++)

for(int j=0; i*j<100005; j++)

{

a[i]+=cnt[i*j];

}

scanf("%d",&q);

while(q--)

{

scanf("%lld%lld",&a1,&a2);

a1=a1*a2/gcd(a1,a2);

scanf("%lld",&a2);

a1=a1*a2/gcd(a1,a2);

scanf("%lld",&a2);

a1=a1*a2/gcd(a1,a2);

if(a1>100000)

printf("%dn",cnt[0]);

else

printf("%dn",a[a1]);

}

}

return 0;

}