文章目录

题解 CF1900D Small GCD

由 hycqwq 发布

赛时没做出来。

第二天把题告诉同机房大佬,想了一天说不会 /ch。

后面看了官方题解,同时感谢这位佬 /bx。

Solution

与官方题解相似。

定义:

  • $m = \max\limits_{j = 1}^n a_j$。
  • $cg_i$ 表示对于任意 $1 \le x < y < z \le n$,$f(a_x, a_y, a_z) = i$ 的 $(x, y, z)$ 个数;
  • $cm_i$ 表示对于任意 $1 \le x < y < z \le n$,$i | f(a_x, a_y, a_z)$ 的 $(x, y, z)$ 个数;
  • $ca_i$ 表示数 $i$ 在 $a$ 中出现的次数;
  • $sa_i = \sum\limits_{1 \le j < i, i | j} ca_j$;
  • $sc_i = \sum\limits_{j = i}^m ca_i$(后缀和)。

答案可表示为:

$$\sum_{j = 1}^m j \cdot cm_j$$

直接求 $cg_i$ 是不容易的,所以我们考虑间接求值。

注意到 $cm_i = \sum\limits_{1 \le j \le m, i |j} cg_j$,可推导出 $cg_i = cm_i - \sum\limits_{i < j \le m, i | j} cg_j$。

于是,我们只需从大到小($m \to 1$)枚举 $i$,算出 $cg_i$ 代入公式即可。


下面讨论 $cm_i$ 的求法。

不妨设 $a_x \le a_y \le a_z$,这导致 $f(a_x, a_y, a_z)$ 与 $a_z$ 无关,所以我们只讨论 $x, y$。

我们知道,若 $i | \gcd(u, v)$,则必有 $i | u, i | v$,反之亦然。

所以,我们要找到 $i | \gcd(a_x, a_y)$ 的方案数,只需找到 $i | a_x, i | a_y$ 的方案数即可。

枚举 $1 \le j \le m, i | j$,考虑取 $j$ 作为 $a_y$ 的情况:

  • 若 $a_x < a_y < a_z$,共有 $sa_j \cdot ca_j \cdot sc_{j + 1}$ 种方案;
  • 若 $a_x < a_y = a_z$,共有 $sa_j \cdot \left(\large^{ca_j}_2\right)$ 种方案;
  • 若 $a_x = a_y < a_z$,共有 $\left(\large^{ca_j}_2\right) \cdot sc_{j + 1}$ 种方案;
  • 若 $a_x = a_y = a_z$,共有 $\left(\large^{ca_j}_3\right)$ 种方案。

上述情况可叠加。

于是这道题就这么愉快地结束啦!

对于每个 $1 \le i \le m$,进行两次步长为 $i$ 的遍历,复杂度为 $O(\lfloor \frac{m}{i}\rfloor)$,而 $\sum\limits_{i = 1}^m \lfloor \frac{m}{i}\rfloor \approx m \log m$,于是总复杂度约为 $O(m \log m)$。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int infi = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
#define elif else if
#define il inline

int t, n, m;
ll ca[100005]; // 每个数的计数器
ll sc[100005]; // ca 的后缀和
ll cg[100005]; // 以每个数为 f 的三元组个数

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        memset(ca, 0, sizeof(ca));
        memset(sc, 0, sizeof(sc));
        memset(cg, 0, sizeof(cg));
        m = 0;
        for (int i = 1, a; i <= n; i++)
            cin >> a, ca[a]++, m = max(m, a);
        for (int i = m; i >= 1; i--)
            sc[i] = sc[i + 1] + ca[i];
        for (int i = m; i >= 1; i--) // 从大到小枚举计算 cg
        {
            // 先计算出 f 为 i 的倍数(或 i)的三元组个数
            // 假设三元组为 (a, b, c) 且 a < b < c
            // 枚举 b
            int sa = 0; // 比目前的 b 小的 a 的个数
            for (int b = i; b <= m; b += i)
            {
                // 选至少一个 b,并且不只是最大的
                if (ca[b] >= 1) // 取 1 个 b
                    // 1 小 + 1 b + 1 大
                    cg[i] += sa * ca[b] * sc[b + 1];
                if (ca[b] >= 2) // 取 2 个 b
                    // 1 小 + 2 b + 0 大 / 0 小 + 2 b + 1 大
                    cg[i] += (ca[b] * (ca[b] - 1) / 2) * (sa + sc[b + 1]);
                if (ca[b] >= 3) // 取 3 个 b
                    // 0 小 + 3 b + 0 大
                    cg[i] += ca[b] * (ca[b] - 1) * (ca[b] - 2) / 6;
                sa += ca[b];
            }
            // 再把所有倍数的都减掉
            for (int j = i * 2; j <= m; j += i)
                cg[i] -= cg[j];
        }
        ll ans = 0;
        for (int i = 1; i <= m; i++)
            ans += cg[i] * i;
        cout << ans << endl;
    }
    return 0;
}

注释写的有点乱,无伤大雅。


仅有一条评论

  1. HiYa
    HiYa · 2023-12-17 16:02
    include include include include include include include include include include include include include include include include

    引这么多函数库是吧(),直接给我整懵了

发表评论