leetcode数论(2447. 最大公因数等于 K 的子数组数目)

 前言

经过前期的数据结构和算法学习，开始以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 <= 1000
• 1 <= 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;}
}

1.QA: