题目 3220 ⭐因数计数⭐【数理基础】蓝桥杯2024年第十五届省赛
小蓝随手写出了含有 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 = 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;
int al = nums;
// 计算满足 ai 是 ak 的因数且 aj 是 al 的因数的 (ai, aj) 的数量
int count_ai = factor_count;
int count_aj = factor_count;
// 排除 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)。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]