2447.最大公因数等于K的子数组数目

链接：2447.最大公因数等于K的子数组数目
难度：Medium
标签：数组、数学、数论
简介：数组的最大公因数 是能整除数组中所有元素的最大整数。

题解 1 - typescript

• 编辑时间：2022-10-23
• 执行用时：88ms
• 内存消耗：42.4MB
• 编程语言：typescript
• 解法介绍：gcd 后暴力。

function gcd(a: number, b: number): number {
  if (a < b) return gcd(b, a);
  if (b) return gcd(b, a % b);
  return a;
}
function subarrayGCD(nums: number[], k: number): number {
  let ans = 0;
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    if (nums[i] === k) {
      ans++;
    }
    let num = nums[i];
    for (let j = i - 1; j >= 0; j--) {
      num = gcd(nums[j], num);
      if (num === k) ans++;
    }
  }
  return ans;
}