CodeForces 632D Longest Subsequence

时间：2023-03-08 17:50:22
CodeForces 632D Longest Subsequence

暴力。

虽然$a[i]$最大有${10^9}$，但是$m$最大只有${10^6}$，因此可以考虑暴力。

记$cnt[i]$表示数字$i$有$cnt[i]$个，记$p[i]$表示以$i$为倍数的情况下，最多能选出多少个数字。

$p[i]$可以暴力计算出来，最后就是找到$p[i]$最大的$i$，然后输出答案。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<bitset>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c=getchar(); x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) {x=x*+c-''; c=getchar();}

}

const int maxn=;

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

vector<int>v;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++)

    {

        if(a[i]>m) continue;

        cnt[a[i]]++;

    }

    for(int i=;i<=;i++)

        for(int j=i;j<=m;j=j+i)

            p[j]=p[j]+cnt[i];

    int mx=; for(int i=;i<=m;i++) mx=max(mx,p[i]);

    int ans; for(int i=m;i>=;i--) if(p[i]==mx) ans=i;

    if(mx==) ans=;

    for(int i=;i<=n;i++) if(ans%a[i]==) v.push_back(i);

    printf("%d %d\n",ans,v.size());

    for(int i=;i<v.size();i++) printf("%d ",v[i]);

    printf("\n");

    return ;

}

相关文章