CF 632D Longest Subsequence

题目描述

Solution

注意到 $m$ 只有 $1e6$，所以我们直接用类似埃氏筛的方法枚举即可

时间复杂度 $O(n\log n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 1000010
using namespace std;

int n, m, a[maxn], cnt[maxn], f[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] <= m) ++cnt[a[i]];
    }
    for (int i = 1; i <= m; ++i)
        for (int j = i; j <= m; j += i) f[j] += cnt[i];
    int p = max_element(f + 1, f + m + 1) - f;
    cout << p << " " << f[p] << "\n";
    for (int i = 1; i <= n; ++i)
        if (p % a[i] == 0) cout << i << " ";
    cout << "\n"; 
    return 0;
}