ZUFE2486 Heap_输入四个正整数a、b、c、n,(a、b、c均小于200,n<=6),求a、b、c的n次方和。输入-CSDN博客

本文链接：https://blog.csdn.net/Jelly_acm/article/details/72820087

本文解析了一道关于批量处理算法的题目，通过预处理和计算最小公倍数的方法，高效地解决了查询特定条件下数字出现次数的问题。适用于n个非负整数的批量处理场景。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

输出

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

样例输入

样例输出

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]);
            else
                printf("%d\n",a[a1]);


        }

    }
    return 0;
}