zufe oj 2486:heap

oj 2486:heap"/>

zufe oj 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
注意：若ai=0,则a,b,c,d无论取何值都成立。ai中可能有相等的元素
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
int f[100002];
using namespace std;
int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}
int main()
{int T;scanf("%d",&T);while(T--){memset(f,0,sizeof(f));int w[11];memset(w,0,sizeof(w));int n,max1=-2,h=0;scanf("%d",&n);for(int i=1;i<=n;i++){int t;scanf("%d",&t);f[t]++;if(t==0)h++;if(t>max1)max1=t;for(int j=2;j<=10;j++)if(t%j==0)w[j]++;}w[1]=n;int Q;scanf("%d",&Q);while(Q--){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);int x=gcd(a,b); x=a*b/x;if(x>max1){printf("%d\n",h);continue;}int y=gcd(x,c);y=x*c/y;if(y>max1){printf("%d\n",h);continue;}x=gcd(y,d);x=y*d/x;if(x>max1){printf("%d\n",h);continue;}int ans=0;if(x<=10){printf("%d\n",w[x]);continue;}for(int i=x;i<=max1;i=i+x){ans+=f[i];}printf("%d\n",ans+h);}}return 0;
}