时间戳

首页 > 解决方案 > 如何有效地找到集合和整数的最大 gcd？

set - 如何有效地找到集合和整数的最大 gcd？

问题描述

给定一组整数S，以及一些包含整数w的问题。

对于每个问题，计算max{gcd(w,x)} (x in S).

还给出了所有数字nw<n,x<n (x in S)的范围，所以.

我试过简单地计算所有的 gcd，但效率不够。我认为关键是做一些预处理，以便每个问题都可以在 O(log n) 或更短的时间内完成。

好吧，这就是我尝试过的：

#include "iostream"
using namespace std;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int n,m,S[1000010],w;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>S[i];
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>w;
        int mx=0;
        for(int j=0;j<n;j++){
            mx=max(mx,gcd(w,S[j]));
        }
        cout<<mx<<endl;
    }
    return 0;
}

标签： setmaxgreatest-common-divisor

解决方案

优化的一个机会是减少要考虑的 S 的子集。由于gcd(w,x)不能大于x，因此可以跳过小于当前最大值的元素。
给定一组整数，我使用set <int> S;：

        for (auto it = S.rbegin(); it != S.rend(); ++it)
            if (*it <= mx)
                break;
            else
                mx = max(mx, gcd(w, *it));

推荐阅读