# [2183. Count Array Pairs Divisible by K](https://leetcode.com/problems/count-array-pairs-divisible-by-k/)
##### tags: `leetcode`

[TOC]

## Description

## Ideas

### way1
* 首先暴力解的話，就是創建兩個for loop 每次都判斷是否整除
* TC(n^2 * log(max_val) )
* TLE

### way2
* 因為此題其實就是在找 k 的因數，所以創建一個memo儲存看過的num所擁有的因數
* 每次計算新的num時，先計算缺少了哪些因素，再去查找memo
* 接著更新memo
* TC(n*k) TLE

class Solution:
    def coutPairs(self, nums: List[int], k: int) -> int:
        
        memo = [0] * (k + 1)
        res = 0
        for n in nums:
            gcd = math.gcd(k, n) # TC = O(log(k+n))
            needed = k // gcd
            for cd in range(needed, k+1, needed): # TC = O(needed) = O(k)
                res += memo[cd]
            memo[gcd] += 1
            
        return res

### way3
* 沒想到還是TLE了...第二層迴圈還是花太多時間
* 這次創建一個array factor直接先儲存1~k的所有因素
* 第二層迴圈小修改
* TC = O((n+k) * k^0.5)

python

class Solution:
    def coutPairs(self, nums: List[int], k: int) -> int:
        factor = [[] for i in range(k+1)]
        for i in range(1, k+1): # TC = O(k)
            for j in range(i, k+1, i): # TC = O(k^0.5)
                factor[j].append(i)
        
        memo = [0] * (k+1)
        res = 0
        for n in nums: # TC = O(n)
            gcd = math.gcd(n, k) 
            res += memo[k // gcd]
            
            for i in factor[gcd]: # TC = O(k^0.5)
                memo[i] += 1
        
        return res

c++

class Solution {
public:
    long long coutPairs(vector<int>& nums, int k) {
        vector<int> factor;
        for(int d = 1; d <= k; ++d) {
            if (k % d == 0)
                factor.push_back(d);
        }
        
        long long res = 0;
        vector<int> memo(k+1, 0);
        
        for (auto n: nums) { // TC = O(n)
            int g = gcd(n, k);
            res += memo[k / g];
            
            for (auto f: factor) { // TC = O(k^0.5)
                if (g % f == 0)
                    ++memo[f];
            }
        }
        return res;
    }
};