【题目描述】
有n个数字a1,a2,a3....an,求max{gcd(ai,aj)}(i!=j)}。gcd(x,y)表示x与y的最大公约数。
【输入格式】
第一行一个整数n.
之后一行n个数,表示a1,a2,a3...an.
【输出格式】
输出一个整数表示答案。
【样例输入】
3
4 3 6
【样例输出】
3
【数据规模与约定】
对于30%的数据,满足n<=1000;
对于100%的数据,满足n<=10000,1<=ai<=10^6.
【算法分析】
算法一:
对于30%的数据,满足n<=1000.
n²暴力枚举ai和aj,求出gcd,统计答案。
算法二:
对于100%的数据,满足n<=10000,1<=ai<=10^6.
首先要预处理,把n个数字的全部因数及其个数统计出来。
接着枚举答案d,如果d作为因数,累计的个数大于等于2,则说明至少有两个数都有d这个因数,找出最大的d,即为答案。时间复杂度O(n*(sqrt(n)))
【核心代码】
for (int i=1;i<=n;++i)
{
int p=sqrt(a[i]);
for(int j=1;j<=p;++j)
if(a[j}%j==0)
{
b[j]++;
b[a[i]/j]++;
}
}
【参考程序】
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int a[N],b[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
int p=sqrt(a[i]);
for(int j=1;j<=p;++j)
if(a[j]%j==0)
{
b[j]++;
b[a[i]/j]++;
}
}
int ans=0;
for(int i=1;i<=100000;++i)
if(b[i]>1) ans=i;
cout<<ans;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)