题意分析

输出n张优惠券所需的平均盒子数量

解题思路

说先需要分析以下n张优惠券所需的平均盒子数量，当$n$为1时，结果显然是$1$，当$n$为$2$时，如果已经取到一张卷，$1/2$概率才能取到两张，当已经取到$k$张卷时，$(n-k)/n$才能取到$k+1$张。因此$E$（$X_n$) = $1 + 1/2 + ... + 1/n$。考虑到题目需要输出分数，因此我们将答案分为分子和分母分别计算

标程

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    int n;
    while (cin >> n) {
        long long nume = 0;
        long long deno = 1;

        for (int k = 1; k <= n; k++) {
            long long new_deno = lcm(deno, k);
            long long mult1 = new_deno / deno;
            long long mult2 = new_deno / k;
            nume = nume * mult1 + mult2;
            deno = new_deno;

            long long g = gcd(nume, deno);
            nume /= g;
            deno /= g;
        }

        nume = n * nume;
        long long g = gcd(nume, deno);
        nume /= g;
        deno /= g;

        long long integer_part = nume / deno;
        long long remainder = nume % deno;

        if (remainder == 0) {
            cout << integer_part << endl;
        } else {
            string int_str = to_string(integer_part);
            string rem_str = to_string(remainder);
            string deno_str = to_string(deno);

            int total_spaces = int_str.length() + 1;
            int rem_len = rem_str.length();
            int deno_len = deno_str.length();
            int padding = deno_len - rem_len;

            cout << string(total_spaces, ' ') << string(padding, ' ') << rem_str << endl;
            cout << int_str << " " << string(deno_len, '-') << endl;
            cout << string(total_spaces, ' ') << deno_str << endl;
        }
    }
    return 0;
}