Educational Codeforces Round 9 D. Longest Subsequence
解法
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; }