LeetCode2183 统计可以被 K 整除的下标对数目

发表于 | 分类于 |
字数统计: 357 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/count-array-pairs-divisible-by-k/

题意

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足数组中两数相乘等于k的下标对的数目

解法

周赛第四题，有思路但没写出来
之前想到了质因数分解，然后计算每个数包含多少质因数
然后想用dp来解，发现质因数的个数数量以及状态表示都写不出来
正解是对每个因子考虑建立factor数组
假设每次计算a和k的最大公约数g，只需要知道前面有多少个数可以被k/g整除就可以得到当前数可形成的下标对数量
预处理k的所有因子（不需要质因子）
每次处理数组中的一个数a时，遍历所有k的因子，如果可以整除a，就把因子对应的值加一

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int gcd(int a, int b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }
    long long coutPairs(vector<int>& nums, int k) {
        map<int, int> factor;
        for (int i = 1; i * i <= k; i++) {
            if (k % i == 0) {
                factor[i] = 0;
                factor[k / i] = 0;
            }
        }
        long long cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            int g = gcd(nums[i], k);
            cnt += factor[k / g];
            for (auto [a, b]: factor) {
                if (nums[i] % a == 0) {
                    factor[a]++;
                }
            }
        }
        return cnt;

    }
};