出题人题解 | #tokitsukaze and RPG#

原题解链接：https://ac.nowcoder.com/discuss/150249

数数xi的个数，用埃筛的方式计数。然后$forfor$一遍找到最大值，再$forfor$一遍统计最大值数量即可。 时间复杂度$O(nlogn)O(nlogn)$。

//
// Created by calabash_boy on 18-10-18.
//
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[91m[%s %3d]: " fmt "\n\033[0m", \
  __func__,__LINE__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define PB(x) push_back(x)
#define rep(i,l,r) for (int i = l,_ = r;i< _;i++)
#define REP(i,l,r) for (int i=l,_=r;i<=_;i++)
#define leave(x) do {cout<<#x<<endl;fflush(stdout);return 0;}while (0);
#define untie do{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}while (0)

typedef long long LL;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 0x3f3f3f3f;
const ll inf_ll = 0x3f3f3f3f3f3f3f3fLL;


/************* header ******************/
const int maxn = 1e6+100;
int cnt[maxn];
int Cnt[maxn];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    rep(i,0,n){
        int temp;
        scanf("%d",&temp);
        cnt[temp]++;
    }
    REP(i,1,1000000){
        if (cnt[i] == 0)continue;
        for (int j=i;j<=k;j+=i){
            Cnt[j]+= cnt[i];
        }
    }
    int max_val = 0,max_cnt = 0;
    REP(i,1,k){
        if (Cnt[i]== max_val)max_cnt ++;
        else if (Cnt[i] > max_val){
            max_val = Cnt[i];
            max_cnt = 1;
        }
    }
    printf("%d %d\n",max_val,max_cnt);


    return 0;
}