2 solutions
-
0
题面描述
塔子哥是某地区粮食公司的老板,最近从当地农场收购了 ( n ) 吨粮食。他需要将这些粮食公平地分配给不确定数量的分销商,采用除不尽向下取整的方法进行分配。输入一个整数 ( n ) 表示粮食吨数,输出不同粮食分配方案的总数。例如,若 ( n = 7 ),则可能的方案数为 ( 4 ),对应分销商数量为 ( 1, 2, 3, 7 ) 吨的分配。
思路:数学
-
首先,我们知道,如果分销商的数量为,那么每个分销商能得到的粮食数量就是(向下取整)。因此,我们需要找到所有可能的。
-
我们可以从1开始,逐渐增大,直到等于。在这个过程中,每增加1,就意味着有一种新的分配方案。
-
当等于时,我们需要特殊处理。因为此时,和是相等的,所以只能算作一种分配方案,而不是两种。
-
最后,我们将所有的分配方案数加起来,就得到了答案。
代码分析
-
输入与数据类型:
- 使用
unsigned long long
类型来存储输入的粮食吨数 ( n ),这是因为 ( n ) 的范围可以达到 ( 4294967295 ),需要足够大的数据类型以避免溢出。
- 使用
-
平方根优化:
- 计算 的平方根,并将结果存储在
sqrt(n)
中。这是为了减少循环次数,只需要遍历到 的值就可以找到所有可能的分销商数量。这样做的原因是,若大于,那么的值会小于,因此已经在之前的循环中处理过。
- 计算 的平方根,并将结果存储在
-
方案计数逻辑:
- 使用一个
for
循环,从 ( 1 ) 开始遍历到sqrtn
。 - 在每次迭代中,检查 是否等于:
- 如果不相等,则说明存在两种不同的分配方案和,因此
ans
加 2。 - 如果相等,说明此时的分销商数量和每个分销商获得的粮食数量相同,这种情况下只算作一种方案,
ans
加 1。
- 如果不相等,则说明存在两种不同的分配方案和,因此
- 使用一个
-
输出结果:
- 最后,输出累积的方案数
ans
。
- 最后,输出累积的方案数
时间复杂度
代码
C++
python代码
Java代码
-
- 1
Information
- ID
- 57
- Time
- 2000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 123
- Accepted
- 33
- Uploaded By