标签： 数学

目标

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

说明：

• 1 <= n <= 50
• 1 <= limit <= 50

思路

将 n 颗糖果分给 3 位小朋友，每个小朋友分到的糖果数量不超过 limit，求分配的方案数。注意，糖果必须分完，比如示例 1，不存在分得糖果数量为 0 的情况。

• 第一个小朋友分到的糖果数为 a ∈ [0, Math.min(n, limit)]
• 第二个小朋友分到的糖果数为 b ∈ [Math.max(0, n - a - limit), Math.min(n - a, limit)]
• 第三个小朋友分到的糖果数为 n - a - b

代码

/**
 * @date 2024-06-01 15:59
 */
public class DistributeCandies2928 {
    public int distributeCandies(int n, int limit) {
        int res = 0;
        // 为第一个小朋友分配有0~limit种可能
        for (int i = 0; i <= limit; i++) {
            // 这时为第二个小朋友可以有n - i种可能，这里不要忘了不能超过limit
            for (int j = 0; j <= Math.min(limit, n - i); j++) {
                // 第三个小朋友，获取剩下的糖果，但不能超过limit
                if(n - i - j <= limit){
                    res++;
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个正整数 n ，开始时，它放在桌面上。在 10^9 天内，每天都要执行下述步骤：

• 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
• 然后，将这些数字放在桌面上。

返回在 10^9 天之后，出现在桌面上的 不同 整数的数目。

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，14 % 3 等于 2 。

示例 1：

输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。

示例 2：

输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。 

说明：

1 <= n <= 100

思路

这虽然是个简单题，但也不是一眼就能看出答案的。甚至条件稍微改一下就变得麻烦了，比如将10^9天改为有限的几天。

说回这道题，开始向桌面上放一个数字，然后需要找到对桌面数字取模余1的数，第二天将其也放在桌面上，如此循环。

对于数字n来说，n-1与1肯定是满足条件的，然后n-1的约数也符合条件。

考虑到是经过10^9天，每一天都可以减1，那么最终桌面上肯定有n-1个数字（除非桌面上一开始就一个数字1）。

代码

直接返回 n == 1 ? 1 : n - 1 即可。