马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题解发布于 个人博客
还没仔细打理，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[x] cnt[x]；再用调和级数罗列的方法在 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[x] mul[x]。
如许我们就可以得到这种情况的答案
∑ c n t [ x ] × m u l [ x ] . \sum\limits cnt[x] \times mul[x]. ∑cnt[x]×mul[x].
对于 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[x] \times (cnt[x] - 1). ∑cnt[x]×(cnt[x]−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[x] mul[x]，因此这种情况的答案为
∑ c n t [ x ] × m u l [ x ] × m u l [ x ] . \sum\limits cnt[x] \times mul[x] \times mul[x]. ∑cnt[x]×mul[x]×mul[x].
考虑 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[x] mul[x] 的过程，同样用 O ( n log n ) O(n\log n) O(nlogn) 的时间预处置处罚出每个数 x x x 的因数个数 − 1 -1 −1，记为 f a c [ x ] fac[x] fac[x]。于是这种情况的答案为
∑ c n t [ x ] × f a c [ x ] × f a c [ x ] . \sum\limits cnt[x] \times fac[x] \times fac[x]. ∑cnt[x]×fac[x]×fac[x].
考虑 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[x] \times fac[x] \times mul[x] \times 2. ∑cnt[x]×fac[x]×mul[x]×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[x] \times mul[x])^2. ∑(cnt[x]×mul[x])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[x] \times mul[x])^2 + (cnt[x] \times mul[x]) \\ &- cnt[x] \times mul[x] \times mul[x] \\ &- cnt[x] \times fac[x] \times fac[x] \\ &- cnt[x] \times fac[x] \times mul[x] \times 2 \\ &+ cnt[x] \times (cnt[x] - 1). \end{align*} ans=x=1∑max(a)(cnt[x]×mul[x])2+(cnt[x]×mul[x])−cnt[x]×mul[x]×mul[x]−cnt[x]×fac[x]×fac[x]−cnt[x]×fac[x]×mul[x]×2+cnt[x]×(cnt[x]−1).
其中 m u l [ x ] mul[x] mul[x] 和 f a c [ x ] fac[x] fac[x] 的含义已经在上面有所解释。
注意这题需要开 __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[x]++;
- }
- std::vector<int> fac(max);
- std::vector<int> mul(max);
- i64 res = 0;
- for (int x = 1; x < max; x++) {
- if (cnt[x] > 0) {
- fac[x] += cnt[x] - 1;
- mul[x] += cnt[x] - 1;
- for (int y = x + x; y < max; y += x) {
- fac[y] += cnt[x];
- mul[x] += cnt[y];
- }
- res += static_cast<i64>(cnt[x]) * mul[x];
- }
- }
- i80 ans = static_cast<i80>(res) * (res + 1);
- for (int x = 1; x < max; x++) {
- if (cnt[x] > 0) {
- ans -= static_cast<i80>(cnt[x]) * mul[x] * mul[x];
- ans -= static_cast<i80>(cnt[x]) * fac[x] * fac[x];
- ans -= static_cast<i80>(cnt[x]) * fac[x] * mul[x] * 2;
- ans += static_cast<i64>(cnt[x]) * (cnt[x] - 1);
- }
- }
- std::cout << ans << "\n";
-
- return 0;
- }
|
