#include<bits/stdc++.h>
using namespace std;
/*
当a<=5e6时,商的取值[1, 5e6]
除数可以让被除数分成若干段
对于除数i, t[k]:加上序列a在[i*k~i*(k+1)]之间出现的次数,使用前缀和可以快速求出
设pj表示商为j的当前被除数的范围
例如 除数是2时.p1 = [2, 3]。 除数是3时,p1=[3,5],重复为3
所以不断更新范围来统计区间的数字个数
*/
const int N = 1e6, M = 5e6;
vector<int> pre(M + 1, 0);
vector<int> t(M + 1, 0);
vector<pair<int, int> > p(M + 1, {-1, -1});
int query(int l, int r) {
    return pre[r] - pre[l - 1];
}

int main()
{
    freopen("div.in", "r", stdin);
    freopen("div.out", "w", stdout);
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for(int i = 1; i <= n; i++) cin >> a[i];
    int mx = 0;
    for(int i = 1; i <= n; i++) mx += (a[i] < N);
    for(int i = 1; i <= n; i++) pre[a[i]] += 1; //数字a[i]出现的次数
    for(int i = 1; i <= M; i++) pre[i] += pre[i-1]; //数字1~i有多少个数字出现

    for(int i = 1; i <= N; i++) { //枚举所有的除数
        for(int j = i, d = 1; j <= M; j += i, d ++) { //j为被除数,d为商
            int L = p[d].first, R = p[d].second;//[L,R]表示商为d时,除数是i时,被除数的范围是多少
            int L2 = j, R2 = min(j + i - 1,  M);//商为d时,被除数固定的范围是[j,j+i-1].
            if(R < L2) { //之前又端点小于固定的范围左端点,则全部累加
                p[d] = {L2, R2};
                t[d] += query(L2, R2);
            }
            else {
                if(R < R2) { //只累加一部分[R+1, R2];
                    p[d] = {L2, R2};
                    t[d] += query(R + 1, R2);
                }
            }
        }
    }
    for(int i = 1; i < t.size(); i++)
        mx = max(mx, t[i]);

    cout << mx;
    return 0;
}

我们还还可以直接枚举商,商的值只能取$[1,5]$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, f[10], tmp, ans=0;
int main(){
	freopen("div.in", "r", stdin);
	freopen("div.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> tmp;
		for(int j = 1; j <= 5; j++)
			f[j] += ((tmp / j) > (tmp % j) && (tmp/1000000 <= j));
	}
	for(int i = 1; i <= 5; i++) ans = max(ans, f[i]);
	cout << ans;
	return 0;
}