Leetcode 2183. 统计可以被 K 整除的下标对数目

1.题目基本信息

1.1.题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：

• 0 <= i < j <= n - 1 且
• nums[i] * nums[j] 能被 k 整除。

1.2.题目地址

https://leetcode.cn/problems/count-array-pairs-divisible-by-k/description

2.解题方法

2.1.解题思路

哈希表 + 辗转相除法求最大公约数

2.2.解题步骤

第一步，统计各个数字的最大公约数的频数

第二步，理论：两个数字的乘积能被k整除 <=> 两个数字各自与k的最大公约数的乘积能被k整除。循环两层遍历最大公约数，获取两两组合的频数乘积的和。在这里，对于合法的(i,j)对，会被枚举两次，(i,j)和(j,i)两对相同；同时对于不合法的(i,i)对，会被枚举一次

第三步，去掉多枚举的不合法的(i,i)对

第四步，result除以2，消除(i,j)和(j,i)重复对的影响，并返回结果

3.解题代码

Python代码

# 辗转相除法求最大公约数
def gcd(m,n):
    maxVal,minVal=max(m,n),min(m,n)
    r=maxVal%minVal
    while r!=0:
        maxVal=minVal
        minVal=r
        r=maxVal%minVal
    return minVal

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        # 第一步，统计各个数字的最大公约数的频数
        frep=Counter([gcd(num,k) for num in nums])
        # print(frep)
        # 第二步，理论：两个数字的乘积能被k整除 <=> 两个数字各自与k的最大公约数的乘积能被k整除。循环两层遍历最大公约数，获取两两组合的频数乘积的和。在这里，对于合法的(i,j)对，会被枚举两次，(i,j)和(j,i)两对相同；同时对于不合法的(i,i)对，会被枚举一次
        result=0
        for x in frep:
            for y in frep:
                if x*y%k==0:
                    result+=frep[x]*frep[y]
        # 第三步，去掉多枚举的不合法的(i,i)对
        for key in frep.keys():
            if key*key%k==0:
                result-=frep[key]
        # 第四步，result除以2，消除(i,j)和(j,i)重复对的影响，并返回结果
        return result//2

C++代码

class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        unordered_map<long long,long long> frep;
        for(long long num:nums){
            long long gcdVal=gcd(num,k);
            if(frep.find(gcdVal)==frep.end()){
                frep[gcdVal]=1;
            }else{
                frep[gcdVal]++;
            }
        }
        long long result=0;
        for(auto iter1:frep){
            for(auto iter2:frep){
                // cout << iter1.first << " " << iter2.second << endl;
                long long x=iter1.first,y=iter2.first;
                if(x*y%k==0){
                    result+=frep[x]*frep[y];
                }
            }
        }
        for(auto iter3:frep){
            long long key=iter3.first;
            if(key*key%k==0){
                result-=frep[key];
            }
        }
        return result/2;
    }
};

4.执行结果