【解题方法】假设当前已经有k种不同的Coupons,那么获得新的Coupons的概率是(n-k)/n,所以需要步数的期望是n/(n-k)。求和可得到答案为nsigma(1/i)!

题目要求用分数表示,那么加个分数类重载就OK了!

【代码君】

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a%b);
}
struct Fraction
{
    long long num;
    long long den;
    Fraction(long long num  = 0, long long den = 1)
    {
        if(den < 0)
        {
            num = -num;
            den = -den;
        }
        assert(den != 0);
        long long g = gcd(abs(num), den);
        this->num = num / g;
        this->den = den / g;
    }
    Fraction operator +(const Fraction &o) const
    {
        return Fraction(num * o.den + den * o.num, den * o.den);
    }
    Fraction operator -(const Fraction &o) const
    {
        return Fraction(num * o.den - den * o.num, den * o.den);
    }
    Fraction operator *(const Fraction &o) const
    {
        return Fraction(num * o.num, den * o.den);
    }
    Fraction operator /(const Fraction &o) const
    {
        return Fraction(num * o.den, den * o.num);
    }
    bool operator <(const Fraction &o) const
    {
        return num * o.den < den * o.num;
    }
    bool operator ==(const Fraction &o) const
    {
        return num * o.den == den * o.num;
    }
};
int solve(long long x)
{
    int t = 0;
    while(x)
    {
        t++;
        x = x/10;
    }
    return t;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        Fraction ans(n,1);
        Fraction tmp(0,1);
        for(int i=1; i<=n; i++)
            tmp=tmp+Fraction(1,i);
        ans=ans*tmp;
        long long a,b,c;
        a=ans.num;
        b=ans.den;
        if(a/b!=0)
        {
            long long gd=gcd(a,b);
            a/=gd;
            b/=gd;
            c=a/b;
            a=a-c*b;
        }
        else
            c=0;
        if(a==0)
            printf("%lld\n",c);
        else
        {
            int l1,l2,l3;
            long long t1=c,t2=a,t3=b;
            l1=0;
            while(t1)
            {
                t1/=10;
                l1++;
            }
            l2=0;
            while(t2)
            {
                t2/=10;
                l2++;
            }
            l3=0;
            while(t3)
            {
                t3/=10;
                l3++;
            }
            if(l1!=0)
            {
                for(int i=0; i<=l1; i++) printf(" ");
                printf("%lld\n",a);
                printf("%lld ",c);
                int len=max(l2,l3);
                for(int i=0; i<len; i++) printf("-");
                printf("\n");
                for(int i=0; i<=l1; i++) printf(" ");
                printf("%lld\n",b);
            }
            else
            {
                printf("%I64d\n",a);
                int len=max(l2,l3);
                for(int i=0; i<len; i++)
                    printf("-");
                printf("\n");
                printf("%I64d\n",b);

            }
        }
    }
    return 0;
}