昆明做网站的公司哪家好seo点击软件手机
前言
经过前期的数据结构和算法学习，开始以OD机考题作为练习题，继续加强下熟练程度。
描述
给你一个整数数组
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 作为最大公因数的子数组。提示：
1 <= nums.length <= 10001 <= nums[i], k <= 109
实现原理与步骤
本体采用枚举的方法。
1.划分连续区间
2.求最大公因数(公约数)
3.连续区间判断最大公约数
实现代码
class Solution {public int subarrayGCD(int[] nums, int k) {int res=0;for(int i=0;i<nums.length;i++){int g=0;for(int j=i;j<nums.length;j++){g=gcd(g,nums[j]); if(g%k!=0)break;if(g==k) res++;}}return res;}public int gcd(int a,int b){while(b!=0){int temp=b;b=a%b;a=temp;}return a;}
}