代刷网站推广,河南快速网站备案,做慧聪网价格网站价格,安卓优化大师官网小蓝随手写出了含有 n n n 个正整数的数组 a 1 , a 2 , ⋅ ⋅ ⋅ , a n {a_1, a_2, , a_n} a1,a2,⋅⋅⋅,an #xff0c;他发现可以轻松地算出有多少个有序二元组 ( i , j ) (i, j) (i,j) 满足 a j a_j aj 是 a i a_i ai 的一个因数。因此他定义一个整数对 …小蓝随手写出了含有 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_mapint, int countFactors(const vectorint nums) {unordered_mapint, 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 vectorint nums) {int n nums.size();if (n 4) return 0;// 统计每个数的因数个数unordered_mapint, 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(n2n∗max_num )。 空间复杂度 哈希表 factor_count 的空间复杂度为 O ( n ) O(n) O(n)。
