每日一题之因数计数

问题描述

小蓝随手写出了含有 nn 个正整数的数组 {a1,a2,⋯ ,an}{a1​,a2​,⋯,an​}，他发现可以轻松地算出有多少个有序二元组 (i,j)(i,j) 满足 ajaj​ 是 aiai​ 的一个因数。因此他定义一个整数对 (x1,y1)(x1​,y1​) 是一个整数对 (x2,y2)(x2​,y2​) 的 “因数” 当且仅当 x1x1​ 和 y1y1​ 分别是 x2x2​ 和 y2y2​ 的因数。他想知道有多少个有序四元组 (i,j,k,l)(i,j,k,l) 满足 (ai,aj)(ai​,aj​) 是 (ak,al)(ak​,al​) 的因数，其中 i,j,k,li,j,k,l 互不相等。

输入格式

输入的第一行包含一个正整数 nn 。

第二行包含 nn 个正整数 a1,a2,⋯,ana1​,a2​,⋯,an​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

#include <bits/stdc++.h> #define int long long #define endl '\n' #define INF 0x3f3f3f3f3f3f3f3f using namespace std; const int N = 100010, P = 100010; int t[N], s[N], b[N]; void solve() { int n; cin >> n; vector<int> a(n); // 读取数组 a，并统计每个数字的出现次数 for (int i = 0; i < n; i++) { cin >> a[i]; t[a[i]]++; // 统计数字 a[i] 出现的次数 } int ans = 0; // 处理所有可能的数字 i for (int i = 1; i <= P; i++) { if (t[i]) { // 如果 i 在数组中出现过 // 遍历 i 的倍数 j for (int j = i * 2; j <= P; j += i) { if (t[j]) { // 如果 j 在数组中出现过 b[i] += t[j]; // 统计 i 作为因数的倍数对 s[j] += t[i]; // 统计 j 作为倍数的因数对 } } // 更新 b[i] 和 s[i]，注意要减去自身 b[i] += t[i] - 1; s[i] += t[i] - 1; ans += t[i] * b[i]; // 计算贡献 } } ans *= (ans + 1); // 计算最终的 ans // 处理 ans 减去冗余的部分 for (int i = 1; i <= P; i++) { if (t[i]) { ans -= b[i] * b[i] * t[i]; ans -= s[i] * s[i] * t[i]; ans -= 2 * s[i] * b[i] * t[i]; ans += t[i] * (t[i] - 1); } } cout << ans; // 输出最终结果 } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); // 调用 solve 函数 return 0; }

大概的思路就是找出所有可能的元组，然后减去i==j，k==l,i==l&&j==k,还有重复的情况。

以上就是大概的代码流程，以2 2 3 6 7为例。当然这道题也可以用暴力的做法，但是时间复杂度肯定会超，因为要用到四个for循环，但是应该能过几个测试点。