Given an integer array nums and an integer k, return the number of subarrays of nums where the greatest common divisor of the subarray's elements is k.
A subarray is a contiguous non-empty sequence of elements within an array.
The greatest common divisor of an array is the largest integer that evenly divides all the array elements.
Example 1:
Input: nums = [9,3,1,2,6,3], k = 3 Output: 4 Explanation: The subarrays of nums where 3 is the greatest common divisor of all the subarray's elements are: - [9,3,1,2,6,3] - [9,3,1,2,6,3] - [9,3,1,2,6,3] - [9,3,1,2,6,3]
Example 2:
Input: nums = [4], k = 7 Output: 0 Explanation: There are no subarrays of nums where 7 is the greatest common divisor of all the subarray's elements.
Constraints:
1 <= nums.length <= 10001 <= nums[i], k <= 109
Related Topics:
Array, Math, Number Theory
Similar Questions:
// OJ: https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int subarrayGCD(vector<int>& A, int k) {
int N = A.size(), ans = 0;
for (int i = 0; i < N; ++i) {
int d = A[i];
for (int j = i; j < N; ++j) {
d = gcd(d, A[j]);
if (gcd(d, k) < k) break;
ans += d == k;
}
}
return ans;
}
};