题意:https://www.luogu.org/problem/show?pid=1291
题解:
假设当前已经得到k个名字,得到第k+1个名字的期望为 <nobr> nn−k </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;
}