题面描述

塔子哥是某地区粮食公司的老板，最近从当地农场收购了 ( n ) 吨粮食。他需要将这些粮食公平地分配给不确定数量的分销商，采用除不尽向下取整的方法进行分配。输入一个整数 ( n ) 表示粮食吨数，输出不同粮食分配方案的总数。例如，若 ( n = 7 )，则可能的方案数为 ( 4 )，对应分销商数量为 ( 1, 2, 3, 7 ) 吨的分配。

思路：数学

1. 首先，我们知道，如果分销商的数量为$i$，那么每个分销商能得到的粮食数量就是$n/i$（向下取整）。因此，我们需要找到所有可能的$i$。

2. 我们可以从1开始，逐渐增大$i$，直到$i$等于$n/i$。在这个过程中，每增加1，就意味着有一种新的分配方案。

3. 当$i$等于$n/i$时，我们需要特殊处理。因为此时，$i$和$n/i$是相等的，所以只能算作一种分配方案，而不是两种。

4. 最后，我们将所有的分配方案数加起来，就得到了答案。

代码分析

1. 输入与数据类型：

   • 使用 unsigned long long 类型来存储输入的粮食吨数 ( n )，这是因为 ( n ) 的范围可以达到 ( 4294967295 )，需要足够大的数据类型以避免溢出。

2. 平方根优化：

   • 计算 $n$ 的平方根，并将结果存储在 sqrt(n) 中。这是为了减少循环次数，只需要遍历到 $sqrt(n)$的值就可以找到所有可能的分销商数量。这样做的原因是，若$i$大于$sqrt(n)$，那么$n/i$的值会小于$sqrt(n)$，因此已经在之前的循环中处理过。

3. 方案计数逻辑：

   • 使用一个 for 循环，从 ( 1 ) 开始遍历到 sqrtn。
   • 在每次迭代中，检查$n/i$ 是否等于$i$：
     • 如果不相等，则说明存在两种不同的分配方案$i$和$n / i$，因此 ans 加 2。
     • 如果相等，说明此时的分销商数量和每个分销商获得的粮食数量相同，这种情况下只算作一种方案，ans 加 1。

4. 输出结果：

   • 最后，输出累积的方案数 ans。

时间复杂度

$O(\sqrt n)$

代码

C++

#include <iostream>
#include <cmath> // 引入cmath库以使用平方根函数
using namespace std;

typedef unsigned long long ull; // 定义一个无符号长整型别名

int main() {
    ull n; // 声明粮食的总吨数
    cin >> n; // 从标准输入读取粮食的总吨数
    ull ans = 0; // 初始化方案计数器
    ull sqrtn = sqrt(n); // 计算n的平方根，优化循环的上限

    // 遍历可能的分销商数量i
    for (ull i = 1; i <= sqrtn; i++) {
        if (n / i != i) { // 如果n // i和i不相等，说明有两种分配方案
            ans += 2; // 增加两种方案
        } else { // 如果n // i等于i
            ans += 1; // 只能算作一种方案
        }
    }

    cout << ans; // 输出最终的方案数
    return 0; // 程序正常结束
}

python代码

n = int(input())  # 从标准输入读取一个整数n，表示粮食的总吨数

i = 1  # 初始化分销商数量i，从1开始
# 当i小于n // i时，继续增加i的值
while i < n // i:
    i += 1  # 每次循环将i增加1，寻找合适的分销商数量

ans = i - 1  # 记录i减去1的值，这表示当i达到n // i之前的分销商数量

# 检查当i等于n // i时的特殊情况
if i == n // i:
    print(ans * 2 + 1)  # 如果相等，方案数为ans的两倍加一
else:
    print(ans * 2)  # 如果不相等，方案数为ans的两倍

Java代码

import java.util.*; // 导入Java的工具库

public class Main {
    static int min = Integer.MAX_VALUE; // 定义一个静态变量min，用于存储最小值（未使用）

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建Scanner对象用于接收输入
        long n = sc.nextLong(); // 从输入中读取一个长整型数n，表示粮食的总吨数
        long res = 0; // 初始化结果变量res，用于计数不同的分配方案
        long i = 1; // 初始化分销商数量i，从1开始

        // 循环条件为i小于等于n/2
        while (i <= n / 2) {
            long num = n / i; // 计算每个分销商可以分到的粮食量
            long yu = n % i; // 计算n除以i的余数
            long s = yu / num; // 计算可增加的分销商数量（s）
            i = i + s + 1; // 更新i的值，增加分销商数量
            res++; // 计数，增加一个有效的分配方案
        }

        System.out.println(res + 1); // 输出最终结果，res加1是因为至少有一个分销商（i=1）
    }
}

题目描述

小明是某地区粮食公司的老板。某天，小明的粮食公司从当地农场收购了 $n$ 吨粮食。

然而，小明面临了一个复杂的任务：他需要将这些粮食平均分配给分销商，以便销售到全镇。但问题在于，分销商的数量是不确定的，他无法确定最终将有多少人参与销售。小明坚持采取公平的方式，所以他决定采用除不尽向下取整的方法来分配粮食。

请你帮小明求出分销商获得不同粮食数量的方案数。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示分销商获得粮食数的可能方案数。

7

4

【样例解释 #1】

分销商数量可能为：$1,2,3,7$；

分得粮食数量分别为：$7,3,2,1$。

说明

$1 \le n \le 4294967295$