题目分析

这是一个赠券收集问题：有 $n$ 种不同的球星名字，每个瓶盖等概率出现一种名字，求集齐所有名字所需的期望瓶数。

---

数学公式

期望值为：

$$E(n) = n \times \left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\right) = n \times H_n $$

其中 $H_n$ 是第 $n$ 个调和数。

---

算法思路

1. 计算调和数 $H_n = \sum_{k=1}^n \frac{1}{k}$ 的分数形式
2. 乘以 $n$ 得到 $E(n)$ 的精确分数
3. 输出格式化：
   • 整数：直接输出
   • 带分数：按样例格式分行输出

---

代码解析

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 计算 H_n = 1/1 + 1/2 + ... + 1/n 的分数形式
    long long up = 0, down = 1;
    
    for (int i = 0; i < n; i++) {
        long long v = n - i;  // 即 k = i+1
        up = up * v + down;   // 通分相加
        down = v * down;
        long long g = __gcd(up, down);  // 约分
        up /= g;
        down /= g;
    }
    
    // E(n) = n × H_n
    up *= n;
    long long g = __gcd(up, down);
    up /= g;
    down /= g;
    
    // 输出结果
    if (down == 1) {
        cout << up;  // 整数情况
        return 0;
    }
    
    // 带分数格式输出
    long long rem = up / down;  // 整数部分
    up = up % down;             // 分数部分
    
    // 格式化输出（对齐）
    int rt = count(rem);
    for (int i = 1; i <= rt + 1; i++) cout << " ";
    cout << up << "\n";
    
    cout << rem << " ";
    int line = count(down);
    for (int i = 1; i <= line; i++) cout << "-";
    cout << "\n";
    
    for (int i = 1; i <= rt + 1; i++) cout << " ";
    cout << down << "\n";
    
    return 0;
}

---

关键步骤

1. 调和数计算

• 从 $1/1$ 开始，依次加 $1/2$, $1/3$, ..., $1/n$
• 每次通分后立即约分，防止溢出

2. 输出格式化

• 整数部分 rem 和小数部分 up/down
• 用空格对齐分数部分
• 横线长度等于分母的数字位数

---

复杂度分析

• 时间复杂度：$O(n^2 \log n)$
  每次通分和约分的代价
• 空间复杂度：$O(1)$
  只存储分子分母

在 $n \leq 1000$ 时完全可行。

---

示例验证

$n=2$：

$$E(2) = 2 \times (1 + \frac{1}{2}) = 3$$

输出：3

$n=5$：

$$E(5) = 5 \times (1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5}) = 11\frac{5}{12} $$

输出格式对齐正确。

该解法通过分数运算精确计算期望值，并按要求格式化输出。