蓝桥杯第十五届CA省赛【因数计数】题解
题解发布于 个人博客还没仔细打理，fork 别人的，等以后有空了改一下代码显示
真题链接
篮球杯官网如今支持 C++17，正式赛不知道是不是还是 C++11。
因数计数
这是比赛里的第四个编程题。
题目大意
给定一个长度为 n n n 的正整数数组 a a a，求有多少个四元组 ( i , j , k , l ) (i, j, k, l) (i,j,k,l) 满意 ( a i , a j ) ∣ ( a k , a l ) (a_i, a_j) \mid (a_k, a_l) (ai,aj)∣(ak,al) 且 i , j , k , l i, j, k, l i,j,k,l 互不相同。
[*]其中 ( a i , a j ) ∣ ( a k , a l ) (a_i, a_j) \mid (a_k, a_l) (ai,aj)∣(ak,al) 表示 a i ∣ a k a_i \mid a_k ai∣ak 且 a j ∣ a l a_j \mid a_l aj∣al;
[*] x ∣ y x \mid y x∣y 表示 x x x 整除 y y y，比方 2 ∣ 4 2 \mid 4 2∣4.
数据范围
[*] 1 ≤ n , a i ≤ 1 0 5 1 \leq n, a_i \leq 10^5 1≤n,ai≤105.
Solution
这题很明显是一道容斥。在满意 ( a i , a j ) ∣ ( a k , a l ) (a_i, a_j) \mid (a_k, a_l) (ai,aj)∣(ak,al) 的根本上，我们令 A B C D E ABCDE ABCDE 分别表示以下几个四元组。
[*] A A A 表示 i ≠ k i \neq k i=k 且 j ≠ l j \neq l j=l;
[*] B B B 表示 i = j i = j i=j;
[*] C C C 表示 i = l i = l i=l;
[*] D D D 表示 j = k j = k j=k;
[*] E E E 表示 k = l k = l k=l.
那么题目要求的答案就是
a n s = A B ‾ C ‾ D ‾ E ‾ = A − B ∪ C ∪ D ∪ E ‾ . ans = A\ \overline{B}\ \overline{C}\ \overline{D}\ \overline{E} = A - \overline{B \cup C \cup D \cup E}. ans=A B C D E=A−B∪C∪D∪E.
我们把后面的一堆 ∪ \cup ∪ 睁开，就会得到
a n s = A − ( A B + A C + A D + A E ) + ( A B C + A B D + A B E + A C D + A C E + A D E ) − ( A B C D + A B C E + A B D E + A C D E ) + A B C D E . \begin{align*} ans = A &- (AB + AC + AD + AE) \\ &+ (ABC + ABD + ABE + ACD + ACE + ADE) \\ &- (ABCD + ABCE + ABDE + ACDE) \\ &+ ABCDE. \end{align*} ans=A−(AB+AC+AD+AE)+(ABC+ABD+ABE+ACD+ACE+ADE)−(ABCD+ABCE+ABDE+ACDE)+ABCDE.
这个式子看着吓人，实在一堆都是 0 0 0，大概有些是可以归并盘算的。
由于 ∩ \cap ∩ 得越多，集合越小，答案就越小，所以我们从下往上看。
首先是 A B C D E ABCDE ABCDE。
将 B C D E BCDE BCDE 代入上面的定义可以得到一个 ( i , i , i , i ) (i, i, i, i) (i,i,i,i) 四元组，与 A A A 的要求抵牾，因此这种情况结果是 0 0 0。
其次是 A B C D ABCD ABCD 这一行。
以 A B C D ABCD ABCD 为例，将 B C D BCD BCD 代入上面的定义，我们会得到 ( i , i , i , i ) (i,i,i,i) (i,i,i,i)，这与 A A A 的要求抵牾。其它三个也都会产生如许的抵牾，因此这四种情况都是 0 0 0。
然后是 A B C ABC ABC 这一行。
我们把 A B C , A B D , A C E , A D E ABC,ABD,ACE,ADE ABC,ABD,ACE,ADE 得到的四元组写到一起
( i , i , k , i ) ( i , i , i , l ) ( i , j , i , i ) ( i , j , j , j ) . \begin{align*} (i, i&, k, i) \\ (i, i&, i, l) \\ (i, j&, i, i) \\ (i, j&, j, j). \end{align*} (i,i(i,i(i,j(i,j,k,i),i,l),i,i),j,j).
不难发现它们均违反了 A A A 的要求，所以这四种都是 0 0 0。
对于 A B E ABE ABE 来说，它产生的四元组是 ( i , i , k , k ) (i,i,k,k) (i,i,k,k)，这就相当于求有多少个二元组 ( i , k ) (i,k) (i,k) 满意 i ≠ k i \neq k i=k 且 a i ∣ a k a_i \mid a_k ai∣ak。
我们可以先用 O ( n ) O(n) O(n) 的时间预处置处罚出每个 x x x 出现了多少次，记为 c n t [ x ] cnt cnt；再用调和级数罗列的方法在 O ( n log n ) O(n\log n) O(nlogn) 的时间内预处置处罚 x x x 的倍数个数 − 1 -1 −1（减一是因为要求 i ≠ k i \neq k i=k），记为 m u l [ x ] mul mul。
如许我们就可以得到这种情况的答案
∑ c n t [ x ] × m u l [ x ] . \sum\limits cnt \times mul. ∑cnt×mul.
对于 A C D ACD ACD 来说，它产生的四元组是 ( i , j , j , i ) (i,j,j,i) (i,j,j,i)，而要求是 a i ∣ a j a_i \mid a_j ai∣aj 且 a j ∣ a i a_j \mid a_i aj∣ai，因此一定有 a i = a j a_i = a_j ai=aj。所以这种情况的答案就是
∑ c n t [ x ] × ( c n t [ x ] − 1 ) . \sum\limits cnt \times (cnt - 1). ∑cnt×(cnt−1).
接着是 A B AB AB 这一行。
考虑 A B AB AB 对应的四元组 ( i , i , k , l ) (i,i,k,l) (i,i,k,l)，要求是 a i ∣ a k a_i \mid a_k ai∣ak 且 a i ∣ a l a_i \mid a_l ai∣al。我们上面预处置处罚了倍数数目 − 1 -1 −1，为 m u l [ x ] mul mul，因此这种情况的答案为
∑ c n t [ x ] × m u l [ x ] × m u l [ x ] . \sum\limits cnt \times mul \times mul. ∑cnt×mul×mul.
考虑 A E AE AE 对应的四元组 ( i , j , k , k ) (i,j,k,k) (i,j,k,k)，要求是 a i ∣ a k a_i \mid a_k ai∣ak 且 a j ∣ a k a_j \mid a_k aj∣ak。我们模仿处置处罚 m u l [ x ] mul mul 的过程，同样用 O ( n log n ) O(n\log n) O(nlogn) 的时间预处置处罚出每个数 x x x 的因数个数 − 1 -1 −1，记为 f a c [ x ] fac fac。于是这种情况的答案为
∑ c n t [ x ] × f a c [ x ] × f a c [ x ] . \sum\limits cnt \times fac \times fac. ∑cnt×fac×fac.
考虑 A C AC AC 对应的 ( i , j , k , i ) (i,j,k,i) (i,j,k,i) 和 A D AD AD 对应的 ( i , j , j , l ) (i,j,j,l) (i,j,j,l)，把要求写开，如下
A C 的要求： a j ∣ a i 且 a i ∣ a k , A D 的要求： a i ∣ a j 且 a j ∣ a l . \begin{align*} AC \ 的要求：a_j \mid a_i \ 且 \ a_i \mid a_k, \\ AD \ 的要求：a_i \mid a_j \ 且 \ a_j \mid a_l. \end{align*} AC 的要求：aj∣ai 且 ai∣ak,AD 的要求：ai∣aj 且 aj∣al.
我们会发现这种要求都是以一个中心数 x x x 为媒介，左右各是 x x x 的因数和倍数。那么这种情况的答案就是
∑ c n t [ x ] × f a c [ x ] × m u l [ x ] × 2. \sum\limits cnt \times fac \times mul \times 2. ∑cnt×fac×mul×2.
末了回到 A A A。
A A A 的盘算就很简朴了，只要 i ≠ k i \neq k i=k 且 j ≠ l j \neq l j=l，这就相当于 A B E ABE ABE 对应的 ( i , i , k , k ) (i,i,k,k) (i,i,k,k) 的答案的平方，即
∑ ( c n t [ x ] × m u l [ x ] ) 2 . \sum\limits (cnt \times mul)^2. ∑(cnt×mul)2.
综上所述。
终极答案
a n s = ∑ x = 1 max ( a ) ( c n t [ x ] × m u l [ x ] ) 2 + ( c n t [ x ] × m u l [ x ] ) − c n t [ x ] × m u l [ x ] × m u l [ x ] − c n t [ x ] × f a c [ x ] × f a c [ x ] − c n t [ x ] × f a c [ x ] × m u l [ x ] × 2 + c n t [ x ] × ( c n t [ x ] − 1 ) . \begin{align*} ans =& \sum\limits_{x = 1}^{\max(a)}(cnt \times mul)^2 + (cnt \times mul) \\ &- cnt \times mul \times mul \\ &- cnt \times fac \times fac \\ &- cnt \times fac \times mul \times 2 \\ &+ cnt \times (cnt - 1). \end{align*} ans=x=1∑max(a)(cnt×mul)2+(cnt×mul)−cnt×mul×mul−cnt×fac×fac−cnt×fac×mul×2+cnt×(cnt−1).
其中 m u l [ x ] mul mul 和 f a c [ x ] fac fac 的含义已经在上面有所解释。
注意这题需要开 __int128。
时间复杂度 O ( n + V log V ) \mathcal{O}(n + V\log V) O(n+VlogV)
[*]其中 V = max ( a ) V = \max(a) V=max(a)。
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using i80 = __int128_t;
using u80 = unsigned __int128_t;
using f64 = double;
using f80 = long double;
constexpr i64 inf = 1E18;
template<class T>
std::istream &operator>>(std::istream &is, std::vector<T> &a) {
for (auto &x: a) {
is >> x;
}
return is;
}
std::ostream &operator<<(std::ostream &os, const i80 &a) {
if (a <= inf) {
return os << i64(a);
}
return os << i64(a / inf) << std::setw(18) << std::setfill('0') << i64(a % inf);
}
i80 power(i80 a, i64 b) {
i80 res = 1;
for ( ; b; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
std::cin >> a;
int max = *std::max_element(a.begin(), a.end()) + 1;
std::vector<int> cnt(max);
for (int x: a) {
cnt++;
}
std::vector<int> fac(max);
std::vector<int> mul(max);
i64 res = 0;
for (int x = 1; x < max; x++) {
if (cnt > 0) {
fac += cnt - 1;
mul += cnt - 1;
for (int y = x + x; y < max; y += x) {
fac += cnt;
mul += cnt;
}
res += static_cast<i64>(cnt) * mul;
}
}
i80 ans = static_cast<i80>(res) * (res + 1);
for (int x = 1; x < max; x++) {
if (cnt > 0) {
ans -= static_cast<i80>(cnt) * mul * mul;
ans -= static_cast<i80>(cnt) * fac * fac;
ans -= static_cast<i80>(cnt) * fac * mul * 2;
ans += static_cast<i64>(cnt) * (cnt - 1);
}
}
std::cout << ans << "\n";
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]