LeetCode 2176. 统计数组中相等且可以被整除的数对

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的 数目 。

示例 1：

输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：

• nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
• nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
• nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
• nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。

1 <= nums.length <= 100
1 <= nums[i], k <= 100

解法一：直接模拟题意：

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if ((nums[i] == nums[j]) && ((i * j) % k == 0)) {
                    ++ans;
                }
            }
        }

        return ans;
    }
};

如果输出数组nums的长度为n，此算法时间复杂度O（n${}^2$），空间复杂度O（1）。

解法二：如果(i * j) % k == 0，有：
$$i=gcd(i,k)\frac{i}{gcd(i,k)}$$
而
$$i\ast j=gcd(i,k)\frac{i}{gcd(i,k)}j=qk（q为整数）$$
两端同时除gcd(i,k)可得：
$$\frac{i}{gcd(i,k)}j=\frac{qk}{gcd(i,k)}$$
又由于以下两式互质：
$$(\frac{i}{gcd(i,k)},\frac{k}{gcd(i,k)})=1$$
因此：
$$j=\frac{pk}{gcd(i,k)}（p为整数）$$
即我们只需要遍历所有下标，对于每个下标i，找到i和k的最大公因数，然后用k除该最大公因数得到g，j就是g的倍数了，然后再看满足nums[i]和nums[j]的个数即符合题意的数对，我们可以先遍历一遍数组，找出每个g的整数倍下标对应的元素值及其个数，遍历时直接加即可：

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        unordered_map<int, unordered_map<int, int>> factorAndNum;

        int maxFactor = nums.size();
        if (k + 1 < maxFactor) {
            maxFactor = k + 1;
        }
        // 第二层循环为调和级数级时间复杂度O（lgn），此处两层循环时间复杂度为O（nlgn）
        for (int i = 1; i < maxFactor; ++i) {
            for (int j = i; j < nums.size(); j += i) {
                ++factorAndNum[i][nums[j]];
            }
        }

        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int factor = k / gcd(i, k);
            
            ans += factorAndNum[factor][nums[i]];
            // 此处需特殊处理0，因为上面预处理时按下标的倍数计算，0的任何倍数都是0
            if (nums[i] == nums[0]) {
                ++ans;
            }
			// 去掉i本身，如果i也是factor的倍数，说明被多计算了一次
            if (i % factor == 0) {
                --ans;
            }
        }
    	// 最后结果需要除2，因为nums[i]==nums[j]时，遍历到i和j分别计算了两次
        return ans / 2;
    }
};

如果输入数组长度为n，此算法时间复杂度为O（nlgn），空间复杂度为（nlgn）。

以上过程中，有一个结论：两个数分别除以这两数的最大公因数，所得的商互质。因为每个数都可以写成若干质数的乘积，最大公因数是取出两个质数池中的公共部分，两个集合中剩下的因数一定互质。如36=2233，24=2223，最大公因数为223=12，剩下的数分别为2和3，是互质的。