首页 > 试题广场 >

来点gcd

[编程题]来点gcd

热度指数：2448 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个有 $n$ 个元素的多重集 $S$ ，有 $m$ 个询问，对于每个询问，给出一个整数 $x$ ，问是否能选择 $S$ 的一个非空子集，满足这个子集的 $gcd$ 等于 $x$ ，当集合只有一个数时，设这个集合的 $gcd$ 就等于这个数， $gcd(x,y)$ 的值为 $x,y$ 的最大公约数

输入描述:

多组数据，先读入一个 T 代表组数
对于每组数据 ：
第一行两个正整数 n , m 分别代表集合包含的元素个数和询问个数
第二行 n 个正整数 ai ，代表集合内的具体元素 ( 1 ≤ ai ≤ n )
接下来 m 行每行一个正整数 x 代表当前询问的数 ( 1 ≤ x ≤ n )
保证 T 组数据中 n，m 的总和不超过 1e6

输出描述:

输出 m 行，每行输出 “YES”  或者  “NO” ( 不包含引号 )

示例1

输入

2
7 3
2 2 6 6 2 1 5
3
2
6
7 3
6 3 1 4 6 4 3
7
5
2

输出

NO
YES
YES
NO
NO
YES

说明

第一组样例
第一个询问 找不到这样的子集
第二个询问 取子集 { 2 }
第三个询问 取子集 { 6 }
第二组样例
第一个询问 找不到这样的子集
第二个询问 找不到这样的子集
第三个询问 取子集 { 4，6 }

算法知识视频讲解

Yui___

这题卡常...

不优化IO会超时

#include <iostream>
#include <vector>

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a%b);
}

int main()
{

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t = 0;
    std::cin>>t;

    while(t--)
    {
        int n = 0,m = 0;
        std::cin>>n>>m;

        std::vector<bool> set(n+1,false),ans(n+1,false);
        for(int i = 1;i <= n;++i)
        {
            int tmp_num = 0;
            std::cin>>tmp_num;
            set[tmp_num] = true;
        }

        for(int i = 1;i <= n;++i)
        {
            int tmp_gcd = 0;
            for(int j = i;j <= n;j+=i)
            {
                if(true == set[j])
                {
                    tmp_gcd = gcd(j,tmp_gcd);
                    if(tmp_gcd == i)
                    {
                        break;
                    }
                }
            }
            if(i == tmp_gcd)
            {
                ans[i] = true;
            }
        }

        for(int i = 0;i < m;++i)
        {
            int query = 0;
            std::cin>>query;
            if(true == ans[query])
            {
                std::cout<<"YES"<<'\n';
            }
            else
            {
                std::cout<<"NO"<<'\n';
            }
        }
    }
}

发表于 2025-11-20 13:44:39 回复(0)

C++

patc

这题是不是卡输入输出,加上cin.tie(0)就过了

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool a[1000005];
inline void solve(){
    int n,m;
    cin>>n>>m;
    int ai;
    for(int i=1;i<=n;i++){
        cin>>ai;
        a[ai]=true;
    }
    for(int i=1;i<=n/2;i++){
        if(a[i]==true)continue;
        int g_sum=0;
        for(int j=i;j<=n;j+=i){
            if(a[j])
            g_sum=gcd(g_sum,j/i);
        }
        if(g_sum==1)a[i]=true;
    }

    while(m--){
        int x;
        cin>>x;
        cout<<(a[x]?"YES\n":"NO\n");
    }
    for(int i=1;i<=n;i++)a[i]=false;
}
int main() {
    int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;

    while (t--) {
        solve();
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-11-20 08:23:32 回复(0)

Java

牛客203596504号

这道题在Java下的计时是不是有点问题，咱先不考虑逻辑对不对，我用以下代码进行计时：

    public static void main(String[] args) {
        long timestamp = System.currentTimeMillis();
        // 中间逻辑代码不用看
        System.out.println(timestamp);
        System.out.println(System.currentTimeMillis());
        System.out.println(System.currentTimeMillis() - timestamp);
    }

输出如下：
1763616350066
1763616350260
194

而判卷结果是：

1/9 组用例通过运行时间1707ms 占用内存18400KB

发表于 2025-11-20 13:34:41 回复(2)

C++

wenqizhi

关于本题复杂度：题解普遍使用的调和级数+求GCD，应该是 $O(n\log^2n)$ ，在 $n$ 达到 $10^6$ 数量级时，仅有 1 秒时限是不是不太好