目录
- 一、概念
- 二、模板
- 三、例题
- 题:1819. 序列中不同最大公约数的数目
- 解:
一、概念
推导:
由算术基本定理得:则,
(1)X (2)得:即:
二、模板
给定两个数 a、b,求它们的最小公倍数。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b; // 先除法,再乘法,避免溢出;
}
三、例题
题:1819. 序列中不同最大公约数的数目
给你一个由正整数组成的数组 nums
。
数字序列的 最大公约数
定义为序列中所有整数的共有约数中的最大整数。
- 例如,序列
[4,6,16]
的最大公约数是2
。
数组的一个 子序列
本质是一个序列,可以通过删除数组中的某些元素(或者不删除)得到。
- 例如,
[2,5,10]
是 [1,2,1,2,4,1,5,10]
的一个子序列。
计算并返回 nums
的所有 非空 子序列中 不同 最大公约数的 数目 。
示例 1:
输入:nums = [6,10,3]
输出:5
解释:上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。
示例 2:
输入:nums = [5,15,40,5,6]
输出:7
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105
解:
解题思路:
AC代码:
class Solution {
static int[] f = new int[200001];
public int countDifferentSubsequenceGCDs(int[] nums) {
int max = Integer.MIN_VALUE;
int res = 0;
for(int num : nums){
f[num] ++;
max = (int)(Math.max(num, max));
res ++;
}
for(int i = 1; i <= max; i ++) {
if(f[i] != 0) continue;
// 枚举该数是否为里面两数的因子,保证因子不一样
int g = 0;
for(int j = i; j <= max; j += i) {
if(f[j] != 0) {
g = gcd(j, g);
if(g == i) break;
}
}
if(g == i) res ++;
}
return res;
}
// 辗转相除法获得最大公约数
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
}