(Educational Codeforces Round 9)Longest Subsequence(dp)

Longest Subsequence
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output
You are given array a with n elements and the number m. Consider some subsequence of a and the value of least common multiple (LCM) of its elements. Denote LCM as l. Find any longest subsequence of a with the value l ≤ m.
A subsequence of a is an array we can get by erasing some elements of a. It is allowed to erase zero or all elements.
The LCM of an empty array equals 1.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the size of the array a and the parameter from the problem statement.
The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of a.
Output
In the first line print two integers l and kmax (1 ≤ l ≤ m, 0 ≤ kmax ≤ n) — the value of LCM and the number of elements in optimal subsequence.
In the second line print kmax integers — the positions of the elements from the optimal subsequence in the ascending order.
Note that you can find and print any subsequence with the maximum length.
Examples
input
7 8 6 2 9 2 7 2 3
output
6 5 1 2 4 6 7
input
6 4 2 2 2 3 3 3
output
2 3 1 2 3
문제의 뜻은 n개의 수를 주고 가장 긴 서열을 찾아야 한다. 서열의 수의 lcm가 m의 문제보다 작게 해야 한다. lcm는 순서와 상관없이, 각각의 수가 몇 개인지 통계하기만 하면 된다.그리고 다시 체법과 같이 한 개의 수의 인자가 얼마나 되는지 체로 쳐라.

#include <bits/stdc++.h>
using namespace std;
int n , m;
int a[1000001] , num[1000001];
int divnum[1000001];
int main()
{
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d" , &a[i]);
        if(a[i] <= m)
        num[a[i]]++;
    }
    for(int i = 1 ; i <= m ; i++)
        if(num[i])
            for(int j = i ; j <= m ; j += i)
                divnum[j] += num[i];
    int maxi = 0;
    for(int i = 1 ; i <= m ; i++)
        if(divnum[i] > divnum[maxi])
            maxi = i;
    if(maxi == 0)
    {
    printf("1 0

");
    return 0;
    }
    printf("%d %d
" , maxi , divnum[maxi]);
    for(int i = 1 ; i <= n ; i++)
        if(maxi % a[i] == 0)
            printf("%d " , i);
    printf("
");
    return 0;
}