632D - Longest Subsequence - CodeForces Solution

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    ll N, M, mx=0, argmx=1;
    cin >> N >> M;
    vector<ll> cnt(M+1), A(N);
    vector<ll> v(M+1);
    for (int i=0; i<N; i++){
        cin >> A[i];
        if(A[i]>M) continue;
        v[A[i]]++;
    }
 
    for (int x=1; x<=M; x++){
        for (int i=x; i<=M; i+=x){
            cnt[i] += v[x];
        }
    }
 
    for (int i=1; i<=M; i++){
        if (cnt[i] > mx){
            mx = cnt[i];
            argmx = i;
        }
    }
 
    vector<int> ans;
    for (int i=0; i<N; i++) if (argmx % A[i] == 0) ans.push_back(i+1);
 
    assert(mx == (ll)ans.size());
    cout << argmx << " " << mx << endl;
    for (auto x : ans) cout << x << " ";
    cout << endl;
 
    return 0;
}