ZUFE2486 Heap
ZUFE2486 Heap
最新推荐文章于 2023-03-25 22:12:10 发布

Jelly_acm 于 2017-05-31 14:37:05 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
2486: Heap
时间限制: 2 Sec 内存限制: 128 MB提交: 16 解决: 5
[ 提交][ 状态][ 讨论版]
题目描述
有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;
}
相关知识
jvm 内存溢出 Java heap space 调优解决过程
String的存储方式
C++ 出现异常“.... \debug
jvm层gc调优
深入JVM 原理(五)Java堆内存调整参数(调优关键)
解读:计数器Counter
室内主要空气污染物与处理方法概述
南开毕业典礼高音版《一路生花》惊艳全场,指尖的樱花如诗写谁的韶华
java之标示符、变量学习(一)
Java基础知识三——数组
原文链接: ZUFE2486 Heap https://m.huajiangbk.com/newsview1520711.html
| 上一篇: 植物“水上漂” | 下一篇: 如何鉴别海金沙 |



