不难想到，可以枚举每个 \(a_i\) 的倍数，并用一个数组统计出现次数，最后求最大值，理论时间复杂度 \(O(n \log n)\)。但如果 \(a_i\) 较小且重复出现，可能退化到 \(O(n^2)\)。因此可以做一个小优化：对于每个 \(a_i \le n\)，提前统计出每个数出现的次数，枚举倍数时只计算一次，可以提升计算效率。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000001],cnt[1000001],b[1000001];
signed main()
{
int T,n,ans;
cin >> T;
while( T -- )
{
ans = 0;
cin >> n;
for( int i = 1 ; i <= n ; i ++ )
b[i] = 0;
for( int i = 1 ; i <= n ; i ++ )
{
cin >> a[i];
if( a[i] <= n ) b[a[i]] ++;
cnt[i] = 0;
}
for( int i = 1 ; i <= n ; i ++ )
for( int j = 0 ; j <= n ; j += i )
cnt[j] += b[i];
for( int i = 1 ; i <= n ; i ++ )
ans = max( ans , cnt[i] );
cout << ans << endl;
}
return 0;
}