题目描述

有n个数， a1, a2, …, an 求出一个S的最大长度，S中包含的数必须属于a1 ~ an，并且集合中任意两个数都是倍数与约数的关系，求S在包含的数的数量最大值是多少。

$n <= 1e5, ai <= 1e7$

• 经典做法 设dp[i]：以i为集合的最大数并且满足S性质的数量最大值，很明显状态转移就是用dp[i]更新它的所以倍数。时间复杂度为O(1e7 logn)时间太紧有可能会超时

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10, M = 1e7 + 10;
int a[N], cnt[M];
int dp[M];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &a[i]);
        cnt[a[i]] ++;
    }
    sort(a, a + n);
    n = unique(a, a + n) - a;
    int res = 0;
    int t = 0;
    if(a[0] == 1)t = cnt[1];
    for(int i = 0; i < n; i ++)
    {
        if(a[i] == 1)continue;
        dp[a[i]] += cnt[a[i]];
        for(int j = 2; j <= a[n - 1] / a[i]; j ++)
            dp[j * a[i]] = max(dp[j * a[i]], dp[a[i]]);
        res = max(res, dp[a[i]]);
    }
    printf("%d", res + t);
    return 0;
}

• 优化做法：根据质数分解定理，只需要枚举每个数的质数倍即可，时间可以降到1e7 * loglog1e7

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10, M = 1e7 + 10;
int primes[M], cnt;
bool st[M];
int a[N], nums[M];
int dp[M];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)break;
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    int maxv = 0;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d", &a[i]);
        maxv = max(a[i], maxv);
        nums[a[i]] ++;
    }
    init(M - 1);
    int res = 0;
    int t = 0;
    for(int i = 1; i <= maxv; i ++)
    {
        dp[i] += nums[i];
        if(!dp[i])continue;
        for(int j = 0; j < cnt && primes[j] <= maxv / i; j ++)
            dp[i * primes[j]] = max(dp[i * primes[j]], dp[i]);
        res = max(res, dp[i]);
    }
    printf("%d", res);
    return 0;
}

总结：对于筛倍数这一类的问题有两种做法
第一种就是筛出每个数的倍数， 设ai <= m 那么时间复杂的为mlogn,注意：枚举的每一个数
第二种就是晒1 ~ m中的所有质因子再筛出1~n中每个数的质数倍，时间复杂度为mloglogm注意：枚举1 ~ m的每一个数