题解：P10390 [蓝桥杯 2024 省 A] 因数计数

· · 题解

因数计数

一道比较（？）好的组合数学题。

使用 cnt[i] 统计 i 的出现频率，suf[i] 表示 i 的倍数的个数（不包括 i 自身），pre[i] 表示 i 的因数的个数（不包括 i 自身）。其中 suf 和 pre 数组可通过 cnt 数组在 O(N\ln N) 复杂度内得出（具体实现看代码即可）。

  1. 首先统计所有的二元组 (i,j)\land i\neq j 的个数 ans ，其中 a_i 是 a_j 的因数。

    • 对于 a_i=a_j ，形成的二元组个数为 A_{cnt[a_i]}^2 。

    • 对于 a_i\neq a_j ，形成的二元组个数为 cnt[a_i]\cdot cnt[a_j] 。

  2. 根据二元组的个数，统计所有可以形成的四元组个数： A_{ans}^2 。

  3. 现在看看我们统计的所有四元组里面有哪些不合法项，现在我们假设两个二元组 (i,j) ， (k,l) 形成了一个四元组 (i,j,k,l) ：

    • 首位数字重复使用（这里的重复是指对同一个下标的数字使用了两次）：如果一个数 x 的 suf[x]>1 ，会出现 i=j 的情况，所占数量为 suf[x]\cdot (suf[x] - 1)\cdot cnt[x] （如 [2,4,6] 会组成四元组 (1,2,1,3)）。 。

    • 末尾数字重复使用：如果一个数 x 的 pre[x]>1 ，会出现 k=l 的情况，所占数量为 pre[x]\cdot (pre[x] - 1)\cdot cnt[x] （如 [2,3,6] 会组成四元组 (1,3,2,3)）。

    • 中间位数字重复使用：如果一个数 x 的 pre[x]>1\land suf[x]>1 ，会出现 j=k 的情况，所占数量为 2\cdot pre[x]\cdot suf[x]\cdot cnt[x] （乘2是因为两个二元组之间有顺序）（如 [2,4,8] 会组成四元组 (1,2,2,3)）。

      由于suf ， pre 数组没有统计 x 自身的个数，我们需要计入下面的不合法项：

    • 对于多次出现的数字 x 的首位，末位，中间位数字重复使用：如果一个数 x 的 (cnt[x]>1\land pre[x]>0)\lor(cnt[x]>1\land suf[x]>0) ，会出现 i=j ， j=k 的情况，所占数量为 4(pre[x]\cdot (pre[x] - 1)\cdot cnt[x]+suf[x]\cdot(suf[x]-1)\cdot cnt[x])（可以计算每种情况出现的次数均为 2\cdot pre/suf[x]\cdot (pre/suf[x] - 1)\cdot cnt[x]）。

    • 如果 cnt[x]>1 ，会出现 i=l\land j=k 的情况，所占数量为 cnt[x] \cdot (cnt[x] - 1) （如 [2,2] 会组成四元组 (1,2,2,1)）。

    • 如果 cnt[x]>2 ，会出现 i=j \lor j=k 的情况，实际上就是三个数字都相同的首位，末位，中间位数字重复使用。各占 2\cdot cnt[x] \cdot (cnt[i] - 1) \cdot (cnt[i] - 2) ，一共 4\cdot cnt[x] \cdot (cnt[i] - 1) \cdot (cnt[i] - 2) （如 [2,2,2] 会组成四元组 (1,1,2,3),(1,2,3,3),(1,2,2,3) 等）。

所有情况统计完毕，将所有四元组的数量减去不合法的情况即可。

代码如下：

// #pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>
#include <thread>
#include <chrono>
#include <random>
#include <numeric>
#include <cstring>
#include <utility>
#include <cassert>

#define fi first
#define se second
using std::cin;
using std::cout;
using std::string;
using PII = std::pair<int, int>;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
const int INF = 0x3f3f3f3f;
const double esp = 1e-5;

template <typename T>
string interage_to_string(T x) {
    string ret;
    while (x) {
        ret += x % 10 + '0';
        x /= 10;
    }
    if (ret.empty()) {
        ret = "0";
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n;
    const int N = 1e5 + 1;
    cin >> n;
    std::vector<int> a(n), cnt(N);
    std::vector<int> pre(N), suf(N);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    u128 ans = 0;
    for (int i = 1; i < N; i++) {
        if (cnt[i]) {
            ans += 1ll * cnt[i] * (cnt[i] - 1);
            for (int j = 2; i * j < N; j++) {
                if (cnt[i * j]) {
                    ans += 1ll * cnt[i] * cnt[i * j];
                    suf[i] += cnt[i * j];
                    pre[i * j] += cnt[i];
                }
            }
        }
    }
    ans = ans * (ans - 1);
    for (int i = 1; i < N; i++) {
        if (!cnt[i]) continue;
        if (suf[i] > 1) {
            ans -= 1ll * suf[i] * (suf[i] - 1) * cnt[i];
        }
        if (pre[i] > 1) {
            ans -= 1ll * pre[i] * (pre[i] - 1) * cnt[i];
        }
        if (pre[i] && suf[i]) {
            ans -= 1ll * cnt[i] * pre[i] * suf[i] * 2;
        }
        if (cnt[i] > 1 && pre[i]) {
            ans -= 1ll * (cnt[i] - 1) * cnt[i] * pre[i] * 2;
            ans -= 1ll * pre[i] * (cnt[i] - 1) * cnt[i] * 2;
        }
        if (cnt[i] > 1 && suf[i]) {
            ans -= 1ll * (cnt[i] - 1) * cnt[i] * suf[i] * 2;
            ans -= 1ll * suf[i] * (cnt[i] - 1) * cnt[i] * 2;
        }
        if (cnt[i] >= 2) {
            ans -= 1ll * cnt[i] * (cnt[i] - 1);
        }
        if (cnt[i] >= 3) {
            ans -= 1ll * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) * 4;
        }
    }
    cout << interage_to_string(ans) << "\n";
    return 0;
}