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

大佬教程收集整理的这篇文章主要介绍了如何有效地找到集合和整数的最大 gcd？，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

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

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

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

还给出了所有数字的范围 n，所以 w<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;
}

解决方法

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

大佬总结

以上是大佬教程为你收集整理的如何有效地找到集合和整数的最大 gcd？全部内容，希望文章能够帮你解决如何有效地找到集合和整数的最大 gcd？所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。