2447. Number of Subarrays With GCD Equal to K
思路与题解
最大公约数,Euclidean algorithms算法证明:
如果我们有2个数: \(a\) 和 \(b\),不妨假设 \(a > b\),当不能整除的情况下,设 \(a = b \times k + c\),其中 \(c < b\)。
通过证明可以得到:\(\text{gcd}(a, b) = \text{gcd}(b, a \; \text{mod} \; b)\)。
证明Step 1:\(a\) 与 \(b\) 的公约数也是 \(a \; \text{mod} \; b\) 的公约数。可以设 \(d | a\) 与 \(d | b\)(\(a=m \times d\),\(d\) 为整数)。显然 \(c = a - b \times k\),可得:\(\frac{c}{d} = \frac{a}{d} - \frac{b}{d} \times k\),\(\frac{a}{d}\) 是整数,\(\frac{b}{d} \times k\) 也是整数,因此 \(\frac{c}{d}\) 也是整数。因此 \(d|c\) 得证,即是 \((c = a \; \text{mod} \; b) | d\) ,正向成立。
证明Step 2:\(b\) 与 \(a \; \text{mod} \; b\) 的公约数也是 \(a\) 的公约数。可以设 \(d | b\) 与 \(d | c\)。可得:\(\frac{a}{d} = \frac{c}{d} - \frac{b}{d} \times k\),其中等式右边同样都是整数,因此 \(\frac{a}{d}\) 也是整数,因此得证。
由于 \(\text{gcd}(a, b) = \text{gcd}(b, a \; \text{mod} \; b)\),自然最大公约数也是相同的。
使用Euclidean algorithms算法计算最大公约数:
public int gcd(int a , int b){
if(b == 0) return a;
return gcd(b , a % b);
}
解法1:暴力法,枚举每一个subarray,计算最大公约数,TLE。
def subarrayGCD(self, nums, k):
if len(nums) == 1:
if nums[0] != k:
return 0
else:
return 1
count = 0
for i in range(len(nums)):
for j in range(i, len(nums)+1):
gcd = math.gcd(*nums[i:j])
if gcd == k:
count += 1
return count
解法2:暴力扫描法。时间复杂度 \(O(n^2)\)。基本思路:维护 nums[i]
与 nums[j]
的gcd,看是不是后面的 j
对应元素的 gcd,如果不是,只会更小就早停;如果是,那是不是和 k
相等,相等就+1。双指针法应该也可以。
public int subarrayGCD(int[] nums, int k) {
if (nums.length == 1) {
if (nums[0] == k) return 1;
else return 0;
}
// 暴力扫描法,计算subarray gcd
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currGCD = 0;
for (int j = i; j < nums.length; j++) {
currGCD = gcd(nums[j], currGCD);
if (currGCD == k) count++;
else if (currGCD < k) break;
}
}
return count;
}
References
[1] OI wiki: 最大公约数
[2] O(N*log(max(nums))) with Explanation | Similar Question
标签:frac,gcd,nums,int,Subarrays,GCD,text,return,2447 From: https://www.cnblogs.com/GradientBoosted/p/17125293.html