蓝桥杯真题解题思路——因数计数

前言

  印象里这题我在 24 年 4 月的蓝桥杯 C++ 本科生 A 组见到过，但是当时我实在太菜了，在赛场上没有想出来。时隔一年我重温这道题，没有借鉴任何人的思路，一上来就奔着 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的复杂度，虽然最后实际上是 O ( n log ⁡ 2 n ) O(n\log^2 n) O(nlog2n) 的复杂度，但也算并独立完成了这道题的求解。这个时间复杂度可能不是最优的，但是应该是比较好理解的。

思路

  首先，我们可以理解一下题目的意思。这里是题目链接。

求解二元组的个数

  首先，题目里提到了一个所谓的“二元组”。

小蓝随手写出了含有 n n n 个正整数的数组 { a 1 , a 2 , ⋯   , a n } \{a_1,a_2,\cdots,a_n\} {a1​,a2​,⋯,an​}，他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i,j) (i,j) 满足 a j a_j aj​ 是 a i a_i ai​ 的一个因数。

  我们肯定要先研究这些二元组，再去研究后面四元组的事情。求解二元组说起来容易，可能是因为小蓝写的数组太小了， O ( n 2 ) O(n^2) O(n2) 的时间复杂度也无所谓。但是限制于本题的数据，我们最好是能找到一种 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的方式求出这些二元组。   那么这样的二元组有多少个呢？我们可以定义一些符号：

p i p_i pi​：满足 a j ( j ≠ i ) a_j(j\neq i) aj​(j=i) 是 a i a_i ai​ 的倍数的 j j j 的个数。即数组里面除了 a i a_i ai​，其它这 n − 1 n-1 n−1 个里面有多少个为 a i a_i ai​ 的倍数。 q i q_i qi​：满足 a j ( j ≠ i ) a_j(j\neq i) aj​(j=i) 是 a i a_i ai​ 的因数的 j j j 的个数。即数组里面除了 a i a_i ai​，其它这 n − 1 n-1 n−1 个里面有多少个为 a i a_i ai​ 的因数。

  显然，这些二元组的总数应为 s = ∑ i = 1 n p i = ∑ i = 1 n q i s=\sum_{i=1}^np_i=\sum_{i=1}^nq_i s=∑i=1n​pi​=∑i=1n​qi​。

为什么 ∑ i = 1 n p i = ∑ i = 1 n q i \sum_{i=1}^np_i=\sum_{i=1}^nq_i ∑i=1n​pi​=∑i=1n​qi​？你可以理解为，当我们找到一个二元组 ( i , j ) (i,j) (i,j) 时， p i p_i pi​ 将增加 1 1 1，而 q j q_j qj​ 也会增加 1 1 1。每发现一个二元组，都会导致 ∑ p \sum p ∑p 和 ∑ q \sum q ∑q 都增加 1 1 1，所以有 ∑ i = 1 n p i = ∑ i = 1 n q i \sum_{i=1}^np_i=\sum_{i=1}^nq_i ∑i=1n​pi​=∑i=1n​qi​。

  那么怎么求解 ∑ i = 1 n p i \sum_{i=1}^np_i ∑i=1n​pi​ 或者 ∑ i = 1 n q i \sum_{i=1}^nq_i ∑i=1n​qi​？我们可以先对数组 a \boldsymbol a a 从小到大排序，这对答案显然不会有影响，排序后的数组仍然记为 a \boldsymbol a a。   接下来令 i i i 从 1 1 1 遍历到 n n n，分别去求解 p i p_i pi​，然后全部求和就是 s s s。说到求解 p i p_i pi​，一个朴素的想法是：遍历 a i + 1 a_{i+1} ai+1​ 到 a n a_n an​，一个一个判断是不是 a i a_i ai​ 的倍数。很遗憾，这种方法时间复杂度过高，为 O ( n 2 ) O(n^2) O(n2)。   那我们不妨换一种思路。我要求 p i p_i pi​，也就是 a i a_i ai​ 的倍数的个数，我可以看数组中等于 2 a i 2a_i 2ai​ 的有多少个，再看等于 3 a i 3a_i 3ai​ 的有多少个……一直这样找下去，然后全部加起来就是 p i p_i pi​。由于现在的 a \boldsymbol a a 是一个升序数组，使用二分查找，可以使得找数组中等于 t a i ta_i tai​ 元素个数的时间复杂度降到 O ( log ⁡ n ) O(\log n) O(logn)。这个 t t t 是从 2 2 2 开始枚举，然后是 3 3 3，那么一直枚举到多少可以结束呢？如果记 a \boldsymbol a a 中最大的元素是 m m m，那么答案是 ⌊ m / a i ⌋ \lfloor m/a_i\rfloor ⌊m/ai​⌋。   根据上面的思路，求解 p i p_i pi​ 的时间复杂度应该是 O ( ( m log ⁡ n ) / a i ) O((m\log n)/a_i) O((mlogn)/ai​)。那么求解 s = ∑ i = 1 n p i s=\sum_{i=1}^np_i s=∑i=1n​pi​，时间复杂度应该就是： O ( ( m log ⁡ n ) ∑ i = 1 n ( 1 / a i ) ) O\left((m\log n)\sum_{i=1}^n(1/a_i)\right) O((mlogn)∑i=1n​(1/ai​))。假设 a i a_i ai​ 互不相等，那么通过基本的放缩，可以知道 ∑ i = 1 n ( 1 / a i ) ≤ ∑ i = 1 n ( 1 / i ) ∼ O ( log ⁡ n ) \sum_{i=1}^n(1/a_i)\leq \sum_{i=1}^n(1/i)\sim O(\log n) ∑i=1n​(1/ai​)≤∑i=1n​(1/i)∼O(logn)，因此求解 s s s 的时间复杂度是 O ( m log ⁡ 2 n ) O(m\log^2n) O(mlog2n)。题目中 m m m 和 n n n 是同上限的，因此也可以将总时间复杂度写作 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)。   那如果 a i a_i ai​ 有重复的，上面的放缩就不成立。但是重复的 a i a_i ai​ 意味着其中某个的 p i p_i pi​ 计算出来了，其它的直接照抄这个 p i p_i pi​ 就行，此时就不需要额外算了。这样时间复杂度还是 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)。   顺带说一句这个 q i q_i qi​，其实顺带就给算完了。比如说我们找到数组中等于 2 a i 2a_i 2ai​ 的元素为 a j a_j aj​ 到 a k a_k ak​。那么 p i p_i pi​ 的变动是增加 k − j + 1 k-j+1 k−j+1，而 q j q_j qj​ 到 q k q_k qk​ 都需要加上 1 1 1。由于每次对数组 q q q 都是在某个连续区间上加上 1 1 1，因此可以构造 q q q 的差分数组 q d i f f \mathit{qdiff} qdiff，保证在常数时间复杂度内完成 q d i f f \mathit{qdiff} qdiff 的修改（否则会拖累时间复杂度到 O ( n 2 ) O(n^2) O(n2)）；所有 a i a_i ai​ 遍历完了之后，使用 O ( n ) O(n) O(n) 的时间从 q d i f f \mathit{qdiff} qdiff 构造 q q q 即可。

求解四元组的个数

  然后题目问我们四元组 ( i , j , k , l ) (i,j,k,l) (i,j,k,l) 有多少个。实际上我是这样想的，先确定了 i i i 和 k k k，在此基础上想一下 ( j , l ) (j,l) (j,l) 有多少种可能？答案是 π ( i , k ) = s − p i − q i − p k − q k + 1 + I ( a i = a k ) \pi(i,k)=s-p_i-q_i-p_k-q_k+1+\mathbb I(a_i=a_k) π(i,k)=s−pi​−qi​−pk​−qk​+1+I(ai​=ak​)。这里的 I ( ⋅ ) \mathbb I(\cdot) I(⋅) 把一个 bool 值转换为整数，意思是当 a i = a k a_i=a_k ai​=ak​ 时， I ( a i = a k ) = 1 \mathbb I(a_i=a_k)=1 I(ai​=ak​)=1，否则 I ( a i = a k ) = 0 \mathbb I(a_i=a_k)=0 I(ai​=ak​)=0。   为什么是这个结果？首先，可以确定 a k a_k ak​ 是 a i a_i ai​ 的倍数。如果我们随便填 ( j , l ) (j,l) (j,l)，显然有 s s s 种填法。然而这其中有一些会导致四元组有重复元素，要抠掉。一共有四种情况需要抠掉：

j = i j=i j=i：此时 l l l 可以填的数字有 p i p_i pi​ 种，所以这种情况有 p i p_i pi​ 种。

j = k j=k j=k：此时 l l l 可以填的数字有 p k p_k pk​ 种，所以这种情况有 p k p_k pk​ 种。

j ≠ i ∧ j ≠ k ∧ l = k j\neq i\wedge j\neq k\wedge l=k j=i∧j=k∧l=k：如果是单纯的 l = k l=k l=k，那么 j j j 有 q k q_k qk​ 种可能，并且这些填法保证 j ≠ k j\neq k j=k。但是由于 a i a_i ai​ 是 a k a_k ak​ 的因数，所以这 q k q_k qk​ 种可能包含 j = i j=i j=i 的情况。那么这种情况就是 q k − 1 q_k-1 qk​−1 种。

j ≠ i ∧ j ≠ k ∧ l = i j\neq i\wedge j\neq k\wedge l=i j=i∧j=k∧l=i：如果是单纯的 l = i l=i l=i，那么 j j j 有 q i q_i qi​ 种可能，并且这些填法保证 j ≠ i j\neq i j=i。

如果 a k a_k ak​ 也是 a i a_i ai​ 的因数（考虑到 a i a_i ai​ 是 a k a_k ak​ 的因数，等价于 a k = a i a_k=a_i ak​=ai​），那么这 q i q_i qi​ 种可能包含 j = k j=k j=k 的情况。如果 a k a_k ak​ 不是 a i a_i ai​ 的因数，那么这 q i q_i qi​ 种可能不包含 j = k j=k j=k 的情况。

因此，这种情况有 q i − I ( a i = a k ) q_i-\mathbb I(a_i=a_k) qi​−I(ai​=ak​) 种。

  那么回到我们的题目，最终四元组的个数就是遍历所有的二元组 ( i , k ) (i,k) (i,k)，并求和 π ( i , k ) \pi(i,k) π(i,k)。可以比表示为 a n s = ∑ ( i , k ) π ( i , k ) = ∑ ( i , k ) [ s − p i − q i − p k − q k + 1 + I ( a i = a k ) ] \mathit{ans}=\sum_{(i,k)}\pi(i,k)=\sum_{(i,k)}[s-p_i-q_i-p_k-q_k+1+\mathbb I(a_i=a_k)] ans=∑(i,k)​π(i,k)=∑(i,k)​[s−pi​−qi​−pk​−qk​+1+I(ai​=ak​)]。   我们可以把上面的和式拆开：

∑ ( i , k ) ( s + 1 ) \sum_{(i,k)}(s+1) ∑(i,k)​(s+1)：这也就是 s ( s + 1 ) s(s+1) s(s+1)。 ∑ ( i , k ) I ( a i = a k ) \sum_{(i,k)}\mathbb I(a_i=a_k) ∑(i,k)​I(ai​=ak​)：数组 a \boldsymbol a a 中值相同的元素分为一组。对于每一组而言，如果这一组有 x x x 个元素，那么这一组的贡献就是 x ( x − 1 ) x(x-1) x(x−1)。由于同一组的元素在排序后的 a \boldsymbol a a 中必连续，所以可以在 O ( n ) O(n) O(n) 复杂度内解决。 − ∑ ( i , k ) ( p i + q i + p k + q k ) -\sum_{(i,k)}(p_i+q_i+p_k+q_k) −∑(i,k)​(pi​+qi​+pk​+qk​)：这就要求我们重新温故一下二元组的求取过程。之前是每找到一个二元组 ( i , k ) (i,k) (i,k)，执行 p i = p i + 1 p_i =p_i+1 pi​=pi​+1 和 q k = q k + 1 q_k=q_k+1 qk​=qk​+1。现在我们每找到一个二元组 ( i , k ) (i,k) (i,k)，都需要计算一下 − ( p i + q i + p k + q k ) -(p_i+q_i+p_k+q_k) −(pi​+qi​+pk​+qk​) 并加入答案。

  最终，我们可以在 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n) 的时间复杂度内求得答案。

AC 代码 import os import sys def make_array(length,val): return [val for _ in range(length)] def make_2d_array(rows,cols,val): return [[val for _ in range(cols)] for _ in range(rows)] def make_3d_array(d1,d2,d3,val): return [[[val for _ in range(d3)] for _ in range(d2)] for _ in range(d1)] def read_int(): return int(input()) def read_ints(): return [int(i) for i in input().split()] from bisect import bisect_left,bisect_right n = read_int() a = sorted(read_ints()) m = max(a) p = make_array(n,-1) q = make_array(n,0) sp = 0 qdiff = make_array(n,0) qdiff[0] = -1 qsum = make_array(n + 1,0) psum = make_array(n + 1,0) ans = 0 for i in range(n): for j in range(1,m // a[i] + 1): target = a[i] * j lidx = bisect_left(a,target) if lidx != n and a[lidx] == target: ridx = bisect_right(a,target) p[i] += ridx - lidx qdiff[lidx] += 1 if ridx < n: qdiff[ridx] -= 1 last = -1;count = 0 for i in range(n): if i == 0: q[0] = qdiff[0] else: q[i] = q[i - 1] + qdiff[i] sp += p[i] if a[i] != last: ans += count * (count - 1) last = a[i] count = 1 else: count += 1 # print(p);print(q);print(qdiff);exit() ans += sp * (sp + 1) + count * (count - 1) # print(ans);exit() for i in range(n): qsum[i + 1] = qsum[i] + q[i] psum[i + 1] = psum[i] + p[i] for i in range(n): ans += 2 * (p[i] + q[i]) for j in range(1,m // a[i] + 1): target = a[i] * j lidx = bisect_left(a,target) if lidx != n and a[lidx] == target: ridx = bisect_right(a,target) ans -= (p[i] + q[i]) * (ridx - lidx) ans -= psum[ridx] - psum[lidx] + qsum[ridx] - qsum[lidx] print(ans)

  上面的代码存在一个漏洞，就是求 s s s 的时候并没有考虑 a i a_i ai​ 重复的情况，容易被卡。但是蓝桥杯还是比较仁慈的，没有这种恶心数据，最终还是过了。当然在比赛的时候，如果有时间，最好能够考虑这种情况，并且改进代码。