# 2470. Number of Subarrays With LCM Equal to K
###### tags: `Leetcode` `Medium` `Math`
Link:
## 思路
和[2447. Number of Subarrays With GCD Equal to K](https://hackmd.io/0-gZfdDARlCFnon9Pibang)很像
java里面没有计算lcm的函数，但我们可以用```LCM(a,b) = (axb) / GCD(a,b)```(参考[这里](https://www.geeksforgeeks.org/program-to-find-lcm-of-two-numbers/))
但c++和python里面可以直接用lcm函数
### 思路一 $O(N^2)$
遍历所有subarray
### 思路二 $O(NK)$
## Code
### O(N^2)

class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            int lcm = nums[i];
            for(int j=i; j<n; j++){
                if(lcm%nums[j]!=0){
                    lcm = getLCM(lcm, nums[j]);
                } 
                if(lcm==k) ans++;
                if(lcm>k) break;
            }
        }
        return ans;
    }
    public int getLCM(int a, int b)
    {
        return (a/gcd(a, b))*b;
    }
    public int gcd(int a, int b){
        if (a==0) return b;
        return gcd(b%a, a);
    }
}

### O(NK)

class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
            Map<Integer, Integer> map1 = new HashMap<>();
            for(int key:map.keySet()){
                int lcm = getLCM(key, nums[i]);
                if(k%lcm==0) map1.put(lcm, map1.getOrDefault(lcm, 0)+map.get(key));
            }
            map = map1;
            ans += map.getOrDefault(k,0);
        }
        return ans;
    }
    public int getLCM(int a, int b)
    {
        return (a/gcd(a, b))*b;
    }
    public int gcd(int a, int b){
        if (a==0) return b;
        return gcd(b%a, a);
    }
}