力扣2183、统计可以被K整除的下标对数目


题目

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

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

思路

  • 数据范围暴力肯定过不了
  • a*b%k == 0
  • 可以得出a与b包含了k的所有因子
  • 我们可以计算整个数组与k的最大公因数,每个数与k的最大公因数有且只有一个
  • 也可以计算k的因子,每个因子有且只有一个互不相同

题解

  • 这里我们采用枚举数组与k的最大公因数

C版本

#define N 100005
typedef long long ll;
int factor_queue[N];
ll factor_bucket[N]; //factor_bucket[key] = value; key=因数,value=因数个数   

int gcd(int a, int b) {
    return a % b ? gcd(b, a % b) : b;
}
long long countPairs(const int* nums, const int numsSize, const int k) {
    int factor_cnt = 0;
 
    
    ll ans = 0;
    for (int i = 0; i < numsSize; ++i) {
        int max_factor = gcd(nums[i], k);
        //printf("gcd(%d, %d) = %d\n", nums[i], k, max_factor);
        if (++factor_bucket[max_factor] == 1) {
            factor_queue[factor_cnt++] = max_factor;
        }
    }
    
    for (int i = 0; i < factor_cnt; ++i) {
        ll factor = factor_queue[i];
        ll factor_num = factor_bucket[factor];

        if ( (factor * factor) % k == 0) ans += (factor_num * (factor_num - 1)) >> 1;
        
        for (int j = i + 1; j < factor_cnt; ++j) {
            ll factor1 = factor_queue[j];
            ll factor_num1 = factor_bucket[factor1];
            if ( (factor * factor1) % k == 0) ans += factor_num * factor_num1;
        }
    }
    memset(factor_bucket, 0, sizeof(factor_bucket)); //力扣判题机制,每次都得初始化
    return ans;
}

C++版本

typedef long long ll;
#define N 100005


class Solution {

private:
    int c[N]; //存储相同因数的个数
    vector<int> dd; //存储不同的因数
public:
    Solution() {
        memset(c, 0, sizeof(c));
    }
    ll countPairs(vector<int>& num, int k) {

        
        int *a = &num[0], n = num.size(), d1 = 0; 
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            int t = gcd(a[i], k);
            if (++c[t] == 1) { // 这个因数第一次出现
                dd.push_back(t);
            }
        }
        d1 = dd.size();//不同因数的个数
        int *d = &dd[0];
        //每个数不同因数的个数只有一个
        for (int i = 0; i < d1; ++i) { 
            ll t1 = d[i], c1 = c[t1];
            if ( (t1 * t1) % k == 0) ans += c1 * (c1-1)/2; //说明有两个数含有相同的因数,那么从这个因数桶不分顺序 取 两个因数
            for (int j = i + 1; j < d1; ++j) { //枚举后面的因数
                ll t2 = d[j], c2 = c[t2];
                if ( (t1 * t2) % k == 0) ans += c1*c2; // 每个因数代表一个数
            }
        }
        return ans;
    }
};
//IO加深
int _IO=[](){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    //cout.tie(0);
    return 0;
}();

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-array-pairs-divisible-by-k


文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录