题解：P10390 [蓝桥杯 2024 省 A] 因数计数
因数计数
一道组合数学题。
使用
-
首先统计所有的二元组
(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) 等）。
-
所有情况统计完毕，将所有四元组的数量减去不合法的情况即可。
代码如下：
// #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;
}