ZUFE2486 Heap

Heap"/>

ZUFE2486 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("%d\n",cnt[0]);elseprintf("%d\n",a[a1]);}}return 0;
}