一道公约数的难题

ACM算法日常

发布于 2022-03-04 04:44:27

25800

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

本次周赛最后一题主要考察对公约数的使用。

题意：给一个数组，任意两个数字相乘，乘积结果可以被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;
    }
};