难度中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3

输出：4

解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：

[9,3,1,2,6,3]

[9,3,1,2,6,3]

[9,3,1,2,6,3]

[9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7

输出：0

解释：不存在以 7 作为最大公因数的子数组。

提示：

# 暴力枚举

	class Solution {
	public int subarrayGCD(int[] nums, int k) {
	int n = nums.length;
	int ans = 0;
	for (int i = 0; i < n; i++) {
	int g = 0;
	// [i ~ j]
	for (int j = i; j < n; j++) {
	// 区间数组的公共最大公约数
	g = gcd(g, nums[j]);

	// 说明不是 k 的倍数，就是 nums [j] 整除不了 k
	// 要满足每个数字都是 k 的倍数
	if (g % k != 0) {
	break;
	}
	//g 必然是 k 的倍数
	// - 若 g == k, 后面满足条件的话，g 依然等于 k
	if (g == k) {
	ans++;
	}
	}
	}
	return ans;
	}

	public int gcd(int a, int b) {
	while (b > 0) {
	int t = a % b;
	a = b;
	b = t;
	}
	return a;
	}

	}

一开始写的代码

	class Solution {
	public int subarrayGCD(int[] nums, int k) {
	int n = nums.length;
	// 9 3 1 2 6 3 12
	int ans = 0;
	for (int i = 0; i < n; i++) {
	if (nums[i] % k != 0) {
	continue;
	}
	boolean f = false;
	if (nums[i] == k) {
	f = true;
	ans++;
	}
	// [i ~ j]
	for (int j = i + 1; j < n; j++) {
	// 当前 j 不行，后面肯定不行
	if (nums[j] % k != 0) {
	break;
	}
	// 有希望
	// 看前面 f 是不是 t : 至少有一个最大公约数是 k
	// 若是就不用在遍历前面的元素，直接下一个
	if (f) {
	ans++;
	} else {
	for (int l = i; l < j; l++) {
	if (gcd(nums[j], nums[l]) == k) {
	ans++;
	f = true;
	break;
	}
	}
	}
	}
	}
	return ans;
	}

	public int gcd(int a, int b) {
	while (b > 0) {
	int t = a % b;
	a = b;
	b = t;
	}
	return a;
	}

	}

# 利用 gcd 的性质

枚举子数组的右端点，去看有多少个不同的 GCD

暴力枚举就是计算了重复的 GCD
由于有大量的重复的 GCD ，需要去重

每个元素不同的 GCD 有 $log(nums[i])$ $l o g (n u m s [i])$ 个
- 一个元素的因子要么是自身
- 要么小于等于该元素的一半
所有子数组至多有 $nlog(U)$ 个不同的 GCD
相同的 GCD 都相邻，在一起

相同的 GCD 都相邻，在一起

由于 GCD 是递增的，所以只需看去重后第一个 GCD 是不是 k
k = 3 ，前面 2 的倍数不能算，需要保存上一次失败元素的下标 fi

每一次 GCD 都用上一次的 GCD 求出当前 GCD

	import java.util.ArrayList;
	import java.util.List;

	class Solution {
	public int subarrayGCD(int[] nums, int k) {
	int n = nums.length;
	int ans = 0;
	//[GCD, 相同 GCD 区间的右端点]
	// 以 i 结尾的 gcd 数组 gs
	List<int[]> gs = new ArrayList<>();
	int fi = -1;
	for (int i = 0; i < n; i++) {
	if (nums[i] % k != 0) {
	fi = i;
	gs.clear();
	continue;
	}
	gs.add(new int[]{nums[i], i});
	int j = 0;
	// 原地去重
	for (int[] g : gs) {
	int gcd = gcd(nums[i], g[0]);
	g[0] = gcd;
	if (gs.get(j)[0] != g[0]) {
	gs.set(++j, g);
	} else {
	// 更新相同 GCD 区间的右端点
	gs.get(j)[1] = g[1];
	}
	}
	// 删除 j 后面的元素
	gs = gs.subList(0, j + 1);
	int[] g = gs.get(0);
	if (g[0] == k) {
	ans += g[1] - fi;
	}
	}
	return ans;
	}

	public int gcd(int a, int b) {
	while (b > 0) {
	int t = a % b;
	a = b;
	b = t;
	}
	return a;
	}

	}

时间复杂度 ： $O(nlogU)$ ， $gcd$ 减半的次数为 $logU$ ，每个数只会被加入数组 $a$ 一次，然后随着新元素加入进来后不断 $gcd$ 变得越来越小，最多减小 $O(logU)$ 次。
空间复杂度 ： $O(logU)$