CF632D

Aryper · 2021-08-11 00:05:22 · 个人记录

Longest Subsequence

关于这个题的神奇解法。

我们针对 c\in[1,m] ，统计数列中有多少 a_i 是其因数。

然后我们比较因数个数，找出因数个数最多且数值较小的那个就是答案。

其实就是对 \operatorname{lcm} 的一个理解。

既然 c 是某些 a_i 的公倍数，假设 c 在拥有因数个数相同的情况下，数值是最小的，那么显然 c 的倍数与其因数个数相同，但因数值问题我们只会选 c ，从而保证 c 是最小的公倍数。

时间复杂度 O(n\log m) 。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;

const ll N=1e6;

struct node{
    ll v,id;
}a[N+5];

ll n,m,cnt,ma,lcm;

ll b[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[++cnt].v=read();a[cnt].id=i;
        if(a[cnt].v>m) cnt--;
    }

    for(ll i=1;i<=cnt;i++) {
        for(ll j=a[i].v;j<=m;j+=a[i].v) {
            b[j]++;
        }
    }

    for(ll i=1;i<=m;i++) {
        if(b[i]>ma) {
            ma=b[i];lcm=i;
        }
    }

    write(lcm);putchar(' ');write(ma);putchar('\n');
    for(ll i=1;i<=cnt;i++) {
        if(lcm%a[i].v==0) {
            write(a[i].id);putchar(' ');
        }
    }

    return 0;
}