关于某道gcd题暴力优化的研究

题目描述
有 n 个数字 a[1],a[2]…a[n]。
求 max{gcd(ai,aj)} ( i!=j ) 。
$n\le 10000$
a i ≤ 1000000 a_i \leq 1000000 ai​≤1000000
这题std很好想，如下：

#include
#include
#include
using namespace std;
int n;
int d[1000005];
int main(){freopen("gcd.in","r",stdin);freopen("gcd.out","w",stdout);scanf("%d",&n);for(int i=1,x;i<=n;i++) scanf("%d",&x),d[x]++;int ans=0;for(int i=1000000;;i--){int num=0;for(int j=1;j*i<=1000000;j++){num+=d[j*i];}if(num>1) {ans=i;break;}}printf("%d\n",ans);return 0;
}

但正如题目写的，我们要研究暴力的优化。
这是普通暴力：

#include
#include
#include
#include
#define N 10010
using namespace std;int gcd(int a,int b) {return (b==0 ? a : gcd(b,a%b));
}inline bool cmp(const int &x,const int &y) {return x>y;
}int n,a[N];int main() {freopen("gcd.in","r",stdin);

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！