F. Clique in the Divisibility Graph - 题解

比赛与标签

比赛: VK Cup 2015 - Finals, online mirror 标签: dp, math, number theory 难度: *1500

题目大意喵~

喵~ 主人 sama，下午好呀！今天我们来攻略一道非常有趣的题目，它把图论和数论巧妙地结合在了一起呢！

题目是这样说的：首先，我们有一个 "整除图" (Divisibility Graph)。图里的每个点都是我们输入集合 A 里的一个正整数。两个点 a 和 b 之间有一条边，当且仅当 a 能被 b 整除，或者 b 能被 a 整除。

然后，我们要在这个图里找到一个 "最大团" (Maximum Clique)。"团" 就是图里的一个点的子集，这个子集里的任意两个点之间都互相有边相连。我们要找的就是包含点数最多的那个团，并输出它的大小。

输入格式:

第一行是一个整数 n，表示集合 A 的大小。
第二行是 n 个不同的正整数，代表集合 A 的元素，而且它们是按升序排列好的哦，真是太贴心了！

输出格式:

输出一个数字，也就是最大团的大小。

举个栗子，如果集合是 {3, 6, 18}，那么 3 整除 6，3 整除 18，6 整除 18。它们两两之间都有整除关系，所以构成了一个大小为 3 的团！

喵喵的解题思路~

初看这题，又是图论又是最大团，可能会觉得有点吓人，因为最大团问题通常是 NP-hard 的说。但是，这里的图很特殊，是 "整除图"，这一定是解题的关键呐！

让我们来思考一下，在一个整除图的 "团" (Clique) 里，元素之间有什么性质呢？假设我们有一个团 {c_1, c_2, ..., c_k}。我们把这些数字从小到大排个序，得到 c_1 < c_2 < ... < c_k。根据团的定义，任意两个元素 c_i 和 c_j (i ≠ j) 之间都有边。这意味着，要么 c_i 整除 c_j，要么 c_j 整除 c_i。因为我们已经排好序了 c_i < c_j，所以 c_j 不可能整除 c_i（除非它们相等，但题目说了数字是不同的）。因此，一定是 c_i 整除 c_j！这个性质对团里任意一对元素都成立。特别是，这意味着 c_1 整除 c_2，c_2 整除 c_3，...，c_{k-1} 整除 c_k。

哇！我们发现了一个惊人的事实：整除图中的一个团，等价于输入集合中的一个子序列，其中每个数都能被它前面的数整除！a_1 | a_2 | a_3 | ... | a_k (这里 | 代表整除)

那么，"最大团" 的大小，不就等于这个 "最长整除链" 的长度了嘛？问题瞬间从一个复杂的图论问题，变成了一个我们更熟悉的序列问题。这种链式递推的关系，是不是让你闻到了动态规划 (DP) 的味道，喵？

好！我们来设计 DP 状态： dp[i] 表示：在给定的数集中，以数字 i 结尾的最长整除链的长度。

那么状态转移方程是什么呢？对于一个存在于输入集合中的数字 i，一个以它结尾的链可以是 ... -> j -> i，其中 j 是 i 的一个约数，并且 j 也必须存在于输入集合中。所以，dp[i] 的值，就应该是所有满足条件的 j 对应的 dp[j] 的最大值，再加上 1 (也就是 i 自己)。 dp[i] = max(dp[j] + 1)，其中 j 是 i 的约数且 j 在输入集合中。如果 i 没有任何约数在集合中，那么 dp[i] 的初始值就是 1（它自己构成一个长度为1的链）。

直接按这个思路，对每个数 i 去找它的所有约数 j，效率可能不够高。我们可以换个角度思考，这正是这道题的精髓所在！

优化思路：类似筛法的DP 我们不去找 "约数"，而是去更新 "倍数"！

我们创建一个 dp 数组，大小为 MAX_VAL + 1，MAX_VAL 是输入数字的最大值（10^6）。
我们先遍历一遍输入的数字，对于每个数字 a，我们知道它本身就可以形成一个长度为 1 的链，所以 dp[a] = 1。
接下来，我们从 i = 1 遍历到 MAX_VAL。
如果 dp[i] 大于 0（说明数字 i 存在于输入集合中，是某个链的结尾），那么 i 就可以作为 "前驱" 去延长别的链。
我们遍历 i 的所有倍数 j = 2*i, 3*i, 4*i, ... 直到 MAX_VAL。
如果某个倍数 j 也存在于输入集合中（即 dp[j] > 0），那么我们就可以用 i 结尾的链来构成一个以 j 结尾的新链。新链的长度是 dp[i] + 1。我们更新 dp[j]： dp[j] = max(dp[j], dp[i] + 1)
因为我们是从小到大遍历 i 的，所以在计算 dp[j] 时，所有 j 的约数 i 的 dp 值都已经计算完毕了。这保证了 DP 的正确性，喵~

最后，整个 DP 过程结束后，dp 数组中的最大值，就是我们要求的答案啦！

代码实现，Let's Go! 喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 输入数字的最大值是 10^6，所以数组开到这个大小
const int MAX_VAL = 1000000;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 用一个布尔数组来快速检查一个数字是否存在于输入中，O(1) 查询！
    // 比每次都去遍历原数组要快得多哦！喵~
    vector<bool> exists(MAX_VAL + 1, false);
    // dp[i] 表示以数字 i 结尾的最长整除链的长度，这是我们DP的核心喵。
    vector<int> dp(MAX_VAL + 1, 0);

    // 读入数据，标记存在的数字，并初始化 dp 值为1（自己本身就是长度为1的链）
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        exists[a] = true;
        dp[a] = 1; // 初始化，任何数自己都是一个长度为1的链
    }

    // 这是我们神奇的DP过程！我们从小到大遍历每个数 i。
    for (int i = 1; i <= MAX_VAL; i++) {
        // 只有当数字 i 存在于输入集合中时，它才能作为链的前驱，才有必要更新它的倍数呐。
        if (exists[i]) {
            // 这里我们遍历 i 的所有倍数 j。就像筛法一样，喵~
            for (int j = 2 * i; j <= MAX_VAL; j += i) {
                // 如果这个倍数 j 也恰好在我们的输入集合里...
                if (exists[j]) {
                    // 我们就可以用 i 结尾的链来延长，形成一条以 j 结尾的新链！
                    // 取个最大值，保证得到的是最长的链~
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }
    }

    int ans = 0;
    // 最后，遍历一遍 dp 数组，找到那个最长的链的长度就是我们的答案啦！
    for (int i = 1; i <= MAX_VAL; i++) {
        if (exists[i]) {
            ans = max(ans, dp[i]);
        }
    }

    // 如果输入为空，ans会是0，但题目保证n>=1，所以至少是1
    if (n > 0 && ans == 0) ans = 1;
    
    cout << ans << endl;

    return 0;
}

复杂度分析

时间复杂度: O(M log M) 的说，其中 M 是输入数字的最大值（这里是 10^6）。外层循环从 1 遍历到 M，内层循环遍历 i 的倍数。总的操作次数大约是 M/1 + M/2 + M/3 + ... + M/M。这是一个调和级数，其和近似于 M * log(M)。所以这个算法非常高效喵！
空间复杂度: O(M) 的说。我们主要用了 exists 和 dp 两个数组，它们的大小都和最大值 M 相关。

喵喵的知识小课堂~

这道题真是太棒了，让我们学到了好多东西呢！

问题转化: 最最关键的一步，就是把抽象的图论 "最大团" 问题，通过分析其内在性质，转化为了数论背景下的 "最长整除链" 问题。看穿问题的本质是解题的第一步哦！
动态规划 (DP): 这是 DP 思想的经典应用。我们定义 dp[i] 为以 i 结尾的最优解，然后通过 i 的约数（或者反过来，用 i 去更新它的倍数）来构建状态转移方程。
筛法思想: 在 DP 转移时，我们没有对每个数 k 去找它的所有约数，而是反过来，对每个数 i 去更新它的所有倍数。这种“正向更新”的思路类似于著名的埃拉托斯特尼筛法 (Sieve of Eratosthenes)，大大提高了效率，是处理约数/倍数问题的常用技巧呐。
空间换时间: 我们用了一个 exists 布尔数组来记录每个数字是否存在，从而将查询一个数是否在集合中的操作从 O(log n) 或 O(n) 降到了 O(1)。这是典型的空间换时间策略，对于数值范围不大的题目，这是个非常好用的方法！

只要多加练习，主人 sama 也一定能成为算法大师的喵！加油~ >w<

F. Clique in the Divisibility Graph - 题解 ​

比赛与标签 ​

题目大意喵~ ​

喵喵的解题思路~ ​

代码实现，Let's Go! 喵~ ​

复杂度分析 ​

喵喵的知识小课堂~ ​