零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第十三天了。
  在刷题的过程中，总结自己遇到的坑点，写出 「 解题报告 」 供他人学习，也是一种自我学习的方式。这就是经典的帮助他人的同时，成就自己。目前， 「 万人千题 」 社区 每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的，也可以来发布你的 「 解题报告 」。千万级流量，你我共同拥有。

一、概念定义

1、模运算

  给定一个正整数 $p$，任意一个整数 $n$，一定存在等式 $n = kp + r$； 其中 $k、r$ 是整数，且满足 $0 \le r \lt p$，称 $k$ 为 $n$ 除以 $p$ 的商， $r$ 为 $n$ 除以 $p$ 的余数，表示成 $n$ (这里采用C++语法，% 表示取模运算)。
  对于正整数和整数 $a$, $b$, 定义如下运算：
    i）取模运算： $a \ mod \ p$，表示 $a$ 除以 $p$ 的余数；
    ii）模 $p$ 加法： $(a + b) \ mod \ p = (a\ mod \ p + b\ mod \ p) \ mod \ p$；
    iii）模 $p$ 减法： $(a - b) \ mod \ p = (a\ mod \ p - b\ mod \ p) \ mod \ p$；
    iv）模 $p$ 乘法： $(a * b) \ mod \ p = ((a \ mod \ p)*(b \ mod \ p)) \ mod \ p$；
    v）幂模 $p$： $(a^b) \ mod \ p = ((a \ mod \ p)^b) \ mod \ p$；
  模运算满足结合律、交换律和分配律。 $a \equiv b (mod\ n)$ 表示 $a$ 和 $b$ 模 $n$ 同余，即 $a$ 和 $b$ 除以 $n$ 的余数相等。

2、最大公约数

  两个数 $a$ 和 $b$ 的最大公约数 (Greatest Common Divisor) 是指同时整除 $a$ 和 $b$ 的最大因子，记为 $gcd(a, b)$。特殊的，当 $gcd(a, b) = 1$，我们称 $a$ 和 $b$ 互素。
  例如，1，2，4 均为 8 和 12 的公约数，最大的公约数就是 4。
  根据算术基本定理，有如下公式满足：

$$a = p_1^{x_1}p_2^{x_2}p_3^{x_3}...p_k^{x_k} \\ b = p_1^{y_1}p_2^{y_2}p_3^{y_3}...p_k^{y_k}$$

那么 $gcd(a,b)$ 可以表示成如下等式：

$$gcd(a,b)=p_1^{min(x_1,y_1)}p_2^{min(x_2,y_2)}p_3^{min(x_3,y_3)}...p_k^{min(x_k,y_k)}$$

  需要说明的是这里的 $a$ 和 $b$ 的分解式中的指数是可以为 0 的。

3、朴素法求最大公约数

  我可以从大到小枚举 $a$ 的约数，然后再判断它是不是 $b$ 的约数，就能找到最大的那个满足条件的约数，就是所求 $gcd$ 了。算法实现如下：

int gcd(int a, int b) {
    int i;
    for(i = a; i >= 2; --i) {
        if(a % i == 0 && b % i == 0)
            return i;
    }
    return 1;
}

  这个算法的时间复杂度是 $O(n)$ 的，算法效率较低，所以，我们需要更加高效的算法。

4、辗转相除法求最大公约数

  首先，当 $b \neq 0$ 时，我们令 $a = kb + r$，其中 $k = \lfloor \frac a b \rfloor$， $r = a \ mod \ b$，并且满足 $(0 \le r < b)$，当一个数 $c$，是 $a$ 的约数，也是 $b$ 的约数，则必然也是 $a-kb$ 的约数，即 $r$ 的约数。自然 $a$ 和 $b$ 的公约数 也就是 $b$ 和 $r$ 的公约数。
  所以， $a$ 和 $b$ 的最大公约数 $=$ $b$ 和 $r$ 的最大公约数。表示为：

$$gcd(a, b) = gcd(b, a \ mod \ b)$$

  但是我们的假设是建立在 $b \neq 0$ 上的，而 $b=0$ 的情况，答案显然就是 $a$ 了。于是对于上面的 $gcd$ 函数，我们可以表示成如下递归式：

$$gcd(a,b) = \begin{cases} a & b=0\\ gcd(b, a \ mod \ b) & b \neq 0 \end{cases}$$

  写成代码，就是：

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

  这里 !是 c/c++ 中的表达式取非的意思，即 真变假，假变真，且 c/c++ 中 0 为假，非0为真；%是取模，即 $mod$ 的程序语法。这个算法的时间复杂度为 $O(log_2n)$。

二、题目描述

  给定一个由 $n(n \le 10^5)$ 个元素组成的正整数数组 $nums$，每个元素的值不超过 $200000$ 。计算并返回 $nums$ 的所有 非空 子序列中 不同 最大公约数 的数目 。

三、算法详解

  对于一个长度为 $n$ 的序列，总共有 $2^n-1$ 个非空子序列；如果枚举所有子序列，并且计算 $gcd$ ，再进行判重，时间复杂度肯定无法接受。
  考虑到数字是有范围的，所以可以枚举所有可能的 $gcd$，当某个子序列的 $gcd$ 等于 $i$ 时，我们去子序列中寻找所有值为 $i$, $2i$, $3i$, … 的数，并且求所有这些数的 $gcd$，如果最后得到的 $gcd$ 正好为 $i$，则说明存在 $i$ 这个gcd，累加和加一。
  其中 $i$ 的范围是 $[1, 200000]$。

四、源码剖析

#define maxn 200001
int has[maxn];

int Max(int a, int b) {
    return a > b ? a : b;                          // (1)
}

int gcd(int a, int b) {
    return !b ? a : gcd(b, a%b);                   // (2)
}

int countDifferentSubsequenceGCDs(int* nums, int numsSize){
    int i, j, t, m = 0, ans = 0;

    memset(has, 0, sizeof(has));                   // (3)
    for(i = 0; i < numsSize; ++i) {
        has[ nums[i] ] = 1;                        // (4)
        m = Max(m, nums[i]);                       // (5)
    }

    for(i = 1; i <= m; ++i) {                      // (6)
        t = 0;
        for(j = i; j <= m; j += i) {               // (7)
            if(has[j])
                t = gcd(t, j);                    
        }
            
        if(t == i)                                 // (8)
            ++ans;
    }
    return ans;
}

• $(1)$ 实现一个函数，求两个数中的最大值；
• $(2)$ 实现一个函数，辗转相除法求最大公约数；
• $(3)$ 初始化所有数都没有在序列中出现过；
• $(4)$ 利用 计数法 标记这个元素是否在序列中是否出现；
• $(5)$ 找出序列中最大的数 $m$；
• $(6)$ 枚举 $i$ 作为某个序列的最大公约数， $i \in [1, m]$；
• $(7)$ 检测所有 $i$ 的倍数是否在序列中存在，并且计算这些数的最大公约数；
• $(8)$ 如果最大公约数正好为 $i$， 说明这就是我们想找的最大公约数，计数器加一；

五、推荐专栏

六、习题练习

请参考原文