一道公约数的难题
本次周赛最后一题主要考察对公约数的使用。
题意：给一个数组，任意两个数字相乘，乘积结果可以被k整除的个数。
例子：
输入：nums = [1,2,3,4,5], k = 2
输出：7
暴力思路
这个题目如果使用暴力解法会超时，暴力解法就是遍历任意两个数字，计算结果能否整除k。复杂度。
优化思路
假设，任意两个数字x、y，如果，那么y有什么特点呢？
显然，我们可以求出k和x的最大公约数6，标准库有gcd函数可以直接求出结果。，也就是说，y只要是4的整数倍就可以和x结合起来被k整除。
有一个特殊情况是，如果，，公约数是2，，此时2的整数倍包括6，如果y取值为6，那么，此时会出现重复计数，需要最后过滤掉。
基于这个特性，我们不难推出解题逻辑：
1 统计数组中所有数字的次数
2 统计所有数字的整数倍的次数s，比如2，那么2、4、6、8...的次数都要算进去
3 通过上面的公约数推算计算y的情况个数
4 过滤特殊情况
5 返回ans/2，因为x和y是对称的
class Solution {
public:
long long coutPairs(vector<int>& nums, int k) {
// 取得最大数字m
int m = *max_element(nums.begin(), nums.end());
// 创建2个数组
vector<long long> cnt(m + 1), s(m + 1);
//统计数字x出现的次数
for (int x : nums) cnt[x] += 1;
// 计算数字i的倍数的数量，比如2，那么2、4、6、8...所有数字的数量
for (int i = 1; i <= m; i += 1)
for (int j = i; j <= m; j += i) {
s[i] += cnt[j];
}
long long ans = 0;
for (int i = 1; i <= m; i += 1) {
// 计算k-24 i-18最大公约数是6，k剩余部分是4
// k-4 i-6
int x = k / gcd(k, i);
if (x <= m) ans += cnt[i] * s[x];
}
// 注意上面gcd出来的x可能是i的约数，这样重复计数了i，这里需要将i去掉
for (long long i = 1; i <= m; i += 1)
if ((long long)i * i % k == 0) ans -= cnt[i];
return ans / 2;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-02-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录