题目 3220 ⭐因数计数⭐【数理基础】蓝桥杯2024年第十五届省赛 ...

星球的眼睛论坛元老 | 2025-4-6 03:06:03 | 显示全部楼层 | 阅读模式

楼主

主题 1312|帖子 1312|积分 3936

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

小蓝随手写出了含有 n n n 个正整数的数组 a 1 , a 2 , ⋅ ⋅ ⋅ , a n {a_1, a_2, · · · , a_n} a1,a2,⋅⋅⋅,an ，他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i, j) (i,j) 满足 a j a_j aj 是 a i a_i ai 的一个因数。因此他定义一个整数对 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 是一个整数对 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 的“因数”当且仅当 x 1 x_1 x1 和 y 1 y_1 y1 分别是 x 2 x_2 x2 和 y 2 y_2 y2的因数。他想知道有多少个有序四元组 ( i , j , k , l ) (i, j, k, l) (i,j,k,l) 满足 ( a i , a j ) (a_i, a_j) (ai,aj) 是 ( a k , a l (a_k, a_l (ak,al) 的因数，此中 i , j , k , l i, j, k, l i,j,k,l 互不相等。
题目分析：

我们必要找到所有满足以下条件的有序四元组 ( i , j , k , l ) (i, j, k, l) (i,j,k,l)：

( a i , a j ) (a_i, a_j) (ai,aj) 是 ( a k , a l ) (a_k, a_l) (ak,al) 的因数，即：
- a i a_i ai 是 a k a_k ak 的因数。
- a j a_j aj 是 a l a_l al 的因数。
i , j , k , l i, j, k, l i,j,k,l 互不相等。

办理思路：

统计每个数的因数关系：
- 对于数组中的每个数 x x x，统计有多少个数是 x x x 的因数。遍历数组，对于每个数 x x x，遍历所有大概的因数 d d d（ d d d 从 1 到 s q r t ( x ) sqrt(x) sqrt(x)），如果 d d d 是 x x x 的因数，则记录 d d d 和 x / d x/d x/d。
- 使用一个哈希表或数组 factor_count 来记录每个数的因数个数。
罗列四元组：
- 对于每一对 ( a k , a l ) (a_k, a_l) (ak,al)，找到所有满足 a i a_i ai 是 a k a_k ak 的因数且 a j a_j aj 是 a l a_l al 的因数的 ( a i , a j ) (a_i, a_j) (ai,aj)。
- 由于 i , j , k , l i, j, k, l i,j,k,l 必须互不相等，必要清除重复的环境。
计算结果：
- 对于每一对 ( a k , a l ) (a_k, a_l) (ak,al)，计算满足条件的 ( a i , a j ) (a_i, a_j) (ai,aj) 的数目，并累加到结果中。
- 如果 a k a_k ak 和 a l a_l al 的因数中包含自己，必要减去重复的环境。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
// 统计每个数的因数个数
unordered_map<int, int> countFactors(const vector<int>& nums) {
unordered_map<int, int> factor_count;
for (int x : nums) {
int count = 0;
for (int d = 1; d <= sqrt(x); d++) {
if (x % d == 0) {
count++;
if (d != x / d) {
count++;
}
}
}
factor_count[x] = count;
}
return factor_count;
}
// 计算满足条件的四元组数量
int countValidQuadruples(const vector<int>& nums) {
int n = nums.size();
if (n < 4) return 0;
// 统计每个数的因数个数
unordered_map<int, int> factor_count = countFactors(nums);
int result = 0;
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++) {
if (k == l) continue; // 确保 k 和 l 不相等
int ak = nums[k];
int al = nums[l];
// 计算满足 ai 是 ak 的因数且 aj 是 al 的因数的 (ai, aj) 的数量
int count_ai = factor_count[ak];
int count_aj = factor_count[al];
// 排除 ai 或 aj 等于 ak 或 al 的情况
if (ak % ak == 0 && al % al == 0) {
count_ai--;
count_aj--;
}
result += count_ai * count_aj;
}
}
return result;
}

复制代码

复杂度分析：

时间复杂度：
- 预处理因数关系： O ( n ∗ m a x _ n u m ) O(n * \sqrt{max\_num}) O(n∗max_num )，此中 n n n 是数组长度， m a x _ n u m max\_num max_num 是数组中的最大值。
- 罗列四元组： O ( n 2 ) O(n^2) O(n2)。
- 总时间复杂度： O ( n 2 + n ∗ m a x _ n u m ) O(n^2 + n * \sqrt{max\_num}) O(n2+n∗max_num )。
空间复杂度：
- 哈希表 factor_count 的空间复杂度为 O ( n ) O(n) O(n)。