Educational Codeforces Round 9 D. Longest Subsequence

問題

codeforces.com

解法

m の値がそこそこ小さいので, m 以下の数 x について, 「x が最小公倍数になるような配列 a の組みあわせはあるのか」というように考えてみます。これは x の約数がなるべく多いものを選べば解決します(これだと例えば 6, 12, 18, ... とかが選ばれてしまうかもしれませんが, こういう場合は最小の 6 を選べば OK)。

各 x について, 約数を列挙して配列 a にいくつ入っているかを調べる, とやると O(N sqrt(M)) かかりますが, 各約数ごとに x に寄与するのはいくつあるか, と考えると, 予め cnt[p] = (配列 a に p という数はいくつあるか)というのを前計算しておけば, 約数 p が x に寄与する数を数えるのは, m/1 + m/2 + ... = m log m で求められます。

裏をかいてまた裏をかく。

const int MAXN = 1000100;
int a[MAXN], cnt[MAXN], scnt[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] <= m) cnt[a[i]]++;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j*i <= m; j++) {
            scnt[i*j] += cnt[i];
        }
    }
    int maxi = 0;
    for (int i = 1; i <= m; i++) maxi = max(maxi, scnt[i]);
    for (int i = 1; i <= m; i++) {
        if (maxi == scnt[i]) {
            cout << i << " " << maxi << endl;
            for (int j = 0; j < n; j++) {
                if (i%a[j] == 0) cout << j+1 << " ";
            }
            cout << endl;
            break;
        }
    }
    return 0;
}