Counting Quacks [CSAcademy #66 C]

https://csacademy.com/contest/round-66/task/counting-quacks/

N匹のアヒルがいる。
i番目のアヒルはX[i]秒毎に鳴く。
T秒までの間で同時に最大何匹のアヒルが鳴くか。
そして、その最大匹数で何回鳴くか。

前提知識

• エラトステネスの篩的な計算量

解法

「cnt[c] := c秒毎に鳴くアヒルが何匹いるか」をまず計算し、同じ間隔で鳴くアヒルはまとめておく。
次に、その全てについて[1,T]の範囲で鳴く部分にその匹数を足していく。
これをやると計算量はN+N/2+N/3+N/4+...となっていくが、これはNlogNとなるのでこれで間に合う。

int N, T, X[101010], V[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> T;
    rep(i, 0, N) cin >> X[i];

    map<int, int> cnt;
    rep(i, 0, N) cnt[X[i]]++;

    fore(p, cnt) for (int i = p.first; i <= T; i += p.first) V[i] += p.second;

    int ans1 = 0, ans2 = 0;
    rep(t, 1, T + 1) {
        if (ans1 < V[t]) {
            ans1 = V[t];
            ans2 = 1;
        }
        else if (ans1 == V[t]) ans2++;
    }
    printf("%d %d\n", ans1, ans2);
}