题意:https://www.luogu.org/problem/show?pid=1291
题解:
假设当前已经得到k个名字,得到第k+1个名字的期望为 <nobr> nnk </nobr> , 所以易得从第一个名字到最后一个名字的平均次数就是 <nobr> ni=1ni </nobr> , 原来这东西就叫做调和级数啊hhh(久仰大名)
PS:这道题的输出我给满分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

int n;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    scanf("%d",&n);
    LL A=0,B=1;
    for(int i=1;i<=n;i++)
    {
        A=A*i+B*n;//A/B+n/i=ai+bn/bi
        B=B*i;
        LL g=gcd(A,B);
        A/=g;
        B/=g;       
    }
    if(B==1) printf("%lld\n",A);
    else
    {
        LL ret=A/B,c=B,rcnt=0,ccnt=0,r=ret;
        while(r) r/=10,rcnt++;
        while(c) c/=10,ccnt++;
        for(int i=1;i<=rcnt;i++) cout<<" ";
        cout<<A-B*ret<<endl<<ret;
        for(int i=1;i<=ccnt;i++) cout<<"-";
        cout<<endl;
        for(int i=1;i<=rcnt;i++) cout<<" ";
        cout<<B<<endl;
    }
    return 0;
}