标签： 数论

3658.奇数和与偶数和的最大公约数

目标

给你一个整数 n。请你计算以下两个值的 最大公约数（GCD）：

sumOdd：最小的 n 个正奇数的总和。

sumEven：最小的 n 个正偶数的总和。

返回 sumOdd 和 sumEven 的 GCD。

示例 1：

输入： n = 4
输出： 4
解释：
前 4 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 = 16
前 4 个偶数的总和 sumEven = 2 + 4 + 6 + 8 = 20
因此，GCD(sumOdd, sumEven) = GCD(16, 20) = 4。

示例 2：

输入： n = 5
输出： 5
解释：
前 5 个奇数的总和 sumOdd = 1 + 3 + 5 + 7 + 9 = 25
前 5 个偶数的总和 sumEven = 2 + 4 + 6 + 8 + 10 = 30
因此，GCD(sumOdd, sumEven) = GCD(25, 30) = 5。

提示：

1 <= n <= 1000

思路

计算最小的 n 个正奇数的和与最小的 n 个正偶数和的最大公约数。

  • (1 + 3 + 5 + …… + 2n - 1) = 2n * n / 2 = n^2
  • (2 + 4 + 6 + …… + 2n) = (2n + 2) * n / 2 = n * (n + 1)

最大公约数为 n。

代码


/**
 * @date 2026-07-15 8:51
 */
public class GcdOfOddEvenSums3658 {

    public int gcdOfOddEvenSums(int n) {
        int oddSum = 0;
        int evenSum = 0;
        for (int k = 0, i = 1, j = 2; k < n; i += 2, j += 2, k++) {
            oddSum += i;
            evenSum += j;
        }
        return gcd(oddSum, evenSum);
    }

    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}

性能

1015.可被K整除的最小整数

目标

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 可能不符合 64 位带符号整数。

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

说明：

  • 1 <= k <= 10^5

思路

求仅包含数字 1 且能够整除正整数 k 的数字的最小长度，如不存在返回 -1。

通俗讲就是多长的 11111…… 能够整除 k。为了防止溢出可以只考虑余数，关键是停止条件是什么？如何确定是否存在？

如果余数出现重复，由于计算的式子不变，后续会陷入循环。可以使用哈希表记录出现过的余数。或者循环 k 次，由于余数的范围只可能是 0 ~ k - 1 共 k 个，如果循环 k 次还没有使余数为 0，那么根据鸽巢原理一定存在重复的余数。

代码


/**
 * @date 2025-11-25 9:26
 */
public class SmallestRepunitDivByK1015 {

    public int smallestRepunitDivByK(int k) {
        if (k == 1) {
            return 1;
        }
        int res = 1;
        int num = 1;
        while (res < k) {
            num = (num * 10 + 1) % k;
            res++;
            if (num == 0) {
                return res;
            }
        }
        return -1;
    }
}

性能

2197.替换数组中的非互质数

目标

给你一个整数数组 nums 。请你对数组执行下述操作：

  1. 从 nums 中找出 任意 两个 相邻 的 非互质 数。
  2. 如果不存在这样的数，终止 这一过程。
  3. 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
  4. 只要还能找出两个相邻的非互质数就继续 重复 这一过程。

返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

思路

将数组 nums 中相邻的非互质的数用它们的最小公倍数替换，一直重复这一过程，返回最终的数组。

遍历数组，针对每一个 num 判断它与其左侧已处理的最后一个值（即 list 的最后一个元素）是否互质，如果不互质，将 num 替换为它们的最小公倍数，同时删除 list 最后一个元素，重复该过程，直到互质为止，最后将 num 加入 list。

代码


/**
 * @date 2025-09-16 8:45
 */
public class ReplaceNonCoprimes2197 {

    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int a : nums) {
            while (!list.isEmpty()) {
                int b = list.get(list.size() - 1);
                int g = gcd(a, b);
                if (g <= 1) {
                    break;
                }
                a = a / g * b;
                list.remove(list.size() - 1);
            }
            list.add(a);
        }
        return list;
    }

}

性能