---
# System prepended metadata

title: 2447. Number of Subarrays With GCD Equal to K
tags: [Leetcode, Medium, Math]

---

# 2447. Number of Subarrays With GCD Equal to K
###### tags: `Leetcode` `Medium` `Math`
Link: https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k/description/
## 思路
### Brute Force $O(N^2)$
gcd的一个性质是如果一个subarray的gcd是```a``` 再加一个element gcd是```b``` ```a```一定大于等于```b```
### Count Past GCD $O(NlogM)$
```M``` is the maximum value in the array
用map记住当前数字之前 所有出现过的gcd和数量
如果当前数字可以被```k```整除 那么说明包含当前数字的subarray gcd有可能等于```k```
所以我们把map里面的所有key都拿出来和当前数字算gcd
最后```map.get(k)```就是以当前数字结尾的gcd=```k```的subarray数量
否则所有包含当前数字的subarray gcd都不可能等于```k```
## Code
Brute Force
```java=
class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            int gcd = nums[i];
            for(int j=i; j<n; j++){
                gcd = gcd(nums[j], gcd);
                if(gcd==k) ans++;
            }
        }
        return ans;
    }
    private int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
}
```
Count Past GCD
```java=
class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums){
            Map<Integer, Integer> temp = new HashMap<>();
            if(num%k==0){
                map.put(num, map.getOrDefault(num, 0)+1);
                for(int key:map.keySet()){
                    int gcd = gcd(key, num);
                    temp.put(gcd, temp.getOrDefault(gcd, 0)+map.get(key));
                }
            }
            ans += temp.getOrDefault(k, 0);
            map = temp;
        }
        return ans;
    }
    private int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
}
```