因数计数

一道组合数学题。

使用

cnt[i]

统计

i

的出现频率，

suf[i]

表示

i

的倍数的个数（不包括

i

自身），

pre[i]

表示

i

的因数的个数（不包括

i

自身）。其中

suf

和

pre

数组可通过

cnt

数组在

O(N\ln N)

复杂度内得出（具体实现看代码即可）。

首先统计所有的二元组 $(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]$ 。
根据二元组的个数，统计所有可以形成的四元组个数： $A_{ans}^2$ 。
现在看看我们统计的所有四元组里面有哪些不合法项，现在我们假设两个二元组 $(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)$ 等）。

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

代码如下：

CPP

// #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;
}

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

文章操作

因数计数

相关推荐

评论

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