题解 CF1900D Small GCD

赛时没做出来。

第二天把题告诉同机房大佬，想了一天说不会 /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;
}

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

• 分类： OI 题解
• 标签： 无标签