题目
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ,返回满足下述条件的下标对 (i, j) 的数目:
- 0 <= i < j <= n - 1 且
- nums[i] * nums[j] 能被 k 整除。
思路
- 数据范围暴力肯定过不了
- a*b%k == 0
- 可以得出a与b包含了k的所有因子
- 我们可以计算整个数组与k的最大公因数,每个数与k的最大公因数有且只有一个
- 也可以计算k的因子,每个因子有且只有一个互不相同
题解
- 这里我们采用枚举数组与k的最大公因数
C版本
#define N 100005
typedef long long ll;
int factor_queue[N];
ll factor_bucket[N]; //factor_bucket[key] = value; key=因数,value=因数个数
int gcd(int a, int b) {
return a % b ? gcd(b, a % b) : b;
}
long long countPairs(const int* nums, const int numsSize, const int k) {
int factor_cnt = 0;
ll ans = 0;
for (int i = 0; i < numsSize; ++i) {
int max_factor = gcd(nums[i], k);
//printf("gcd(%d, %d) = %d\n", nums[i], k, max_factor);
if (++factor_bucket[max_factor] == 1) {
factor_queue[factor_cnt++] = max_factor;
}
}
for (int i = 0; i < factor_cnt; ++i) {
ll factor = factor_queue[i];
ll factor_num = factor_bucket[factor];
if ( (factor * factor) % k == 0) ans += (factor_num * (factor_num - 1)) >> 1;
for (int j = i + 1; j < factor_cnt; ++j) {
ll factor1 = factor_queue[j];
ll factor_num1 = factor_bucket[factor1];
if ( (factor * factor1) % k == 0) ans += factor_num * factor_num1;
}
}
memset(factor_bucket, 0, sizeof(factor_bucket)); //力扣判题机制,每次都得初始化
return ans;
}
C++版本
typedef long long ll;
#define N 100005
class Solution {
private:
int c[N]; //存储相同因数的个数
vector<int> dd; //存储不同的因数
public:
Solution() {
memset(c, 0, sizeof(c));
}
ll countPairs(vector<int>& num, int k) {
int *a = &num[0], n = num.size(), d1 = 0;
ll ans = 0;
for (int i = 0; i < n; ++i) {
int t = gcd(a[i], k);
if (++c[t] == 1) { // 这个因数第一次出现
dd.push_back(t);
}
}
d1 = dd.size();//不同因数的个数
int *d = &dd[0];
//每个数不同因数的个数只有一个
for (int i = 0; i < d1; ++i) {
ll t1 = d[i], c1 = c[t1];
if ( (t1 * t1) % k == 0) ans += c1 * (c1-1)/2; //说明有两个数含有相同的因数,那么从这个因数桶不分顺序 取 两个因数
for (int j = i + 1; j < d1; ++j) { //枚举后面的因数
ll t2 = d[j], c2 = c[t2];
if ( (t1 * t2) % k == 0) ans += c1*c2; // 每个因数代表一个数
}
}
return ans;
}
};
//IO加深
int _IO=[](){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
return 0;
}();
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-array-pairs-divisible-by-k