# 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)$

用map记住当前数字之前 所有出现过的gcd和数量
如果当前数字可以被```k```整除 那么说明包含当前数字的subarray gcd有可能等于```k```
所以我们把map里面的所有key都拿出来和当前数字算gcd
最后```map.get(k)```就是以当前数字结尾的gcd=```k```的subarray数量
否则所有包含当前数字的subarray gcd都不可能等于```k```
## Code
Brute Force

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

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);
}
}