解法一: 质因子分解
可以证明:最多的公约数必然可以是质数
时间复杂度: $O(n \sqrt n) $
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 100010;
int a[N];
int n;
unordered_map<int, int> Hash; // Hash维护每个质因子的个数
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
for (int j = 2; j * j <= a[i]; j ++ )
{
if (a[i] % j == 0)
{
Hash[j] ++ ;
while (a[i] % j == 0) a[i] /= j; // 当出现j * j > a[i]时,for-loop就跳过了
}
}
if(a[i] > 1) Hash[a[i]] ++ ; // 漏网之鱼
}
int res = 1;
for (auto x : Hash)
if(x.second > res) res = x.second;
cout << res << endl;
return 0;
}
解法二 :筛法
逆向思维,枚举公约数。比如d (2~N)是一个公约数,则看a[N]中是否有d、2d、3d、…
$$ s = cnt[d] + cnt[2d] + cnt[3d] + … $$
每个数枚举 $ \frac N d $ 次, $ \frac N 2 + \frac N 3 + … + \frac N N $ 调和级数
时间复杂度: $O (n\log n) $
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int cnt[N];
int main()
{
cin >> n;
while (n -- )
{
int x;
cin >> x;
cnt[x] ++ ;
}
int res = 1;
for (int d = 2; d <= N; d ++ )
{
int s = 0; // 维护d出现的次数
for (int i = d; i <= N; i += d) s += cnt[i];
res = max(res, s);
}
cout << res << endl;
return 0;
}