目录
- 一、概念
- 二、模板
- 三、例题
- 题：1979. 找出数组的最大公约数
- 解：
- 题：LCP 02. 分式化简
- 解：
- 题：1819. 序列中不同最大公约数的数目
- 解：
一、概念
二、模板
三、例题
题：1979. 找出数组的最大公约数
给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。
两个数的 最大公约数 是能够被两个数整除的最大正整数。
示例 1：
输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
示例 2：
输入：nums = [7,5,6,8,3]
输出：1
解释：
nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1
示例 3：
输入：nums = [3,3]
输出：3
解释：
nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3
提示：
2 <= nums.length <= 1000
1 <= nums[i] <= 1000
解：
解题思路：辗转相除法
AC代码：
class Solution {
public int findGCD(int[] nums) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int num : nums) {
max = Math.max(max, num);
min = Math.min(min, num);
}
return gcd(min, max);
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}题：LCP 02. 分式化简
有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？
连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。
输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
示例 1：
输入：cont = [3, 2, 0, 2]
输出：[13, 4]
解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。
示例 2：
输入：cont = [0, 0, 3]
输出：[3, 1]
解释：如果答案是整数，令分母为1即可。
限制：
cont[i] >= 0
1 <= cont的长度 <= 10
cont最后一个元素不等于0
答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。
解：
解题思路：模拟
AC代码：
class Solution {
public int[] fraction(int[] cont) {
int len = cont.length;
int a = 1; // 分子
int b = cont[len - 1]; // 分母
if(len == 1) return new int[] {b, a}; // 特殊情况处理
for(int i = len - 2; i >= 0; i --) {
a += cont[i] * b;
if(i > 0) { // 分子分母颠倒
int t = b;
b = a;
a = t;
}
}
int x = gcd(a, b);
return new int[] {a / x, b / x};
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % 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代码：