博客

题目描述

……在2003年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，更可以赴日韩观看世界杯。还不赶快行动！……”

你关上电视，心想：假设有n个不同球星的名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

题目大意

略

数据范围

2<=n<=33

样例输入

5

样例输出

11(5/12)

解题思路

假设当前已经收集了i的球员的瓶盖，如果要收集第i+1个球员的瓶盖概率为1-i/n。设f[i]为收集i个球员的瓶盖的期望瓶数。

f[i]=1*(1-i/n)+(f[i]+1)*(i/n)

f[i]=(1-i/n)+f[i]*(i/n)+i/n;

f[i]*(1-i/n)=1-i/n+1/n

f[i]=1/(1-i/n)

f[i]=n/(n-i)

所以答案就是

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
long long A=0,B=1,GCD,LCM,t;
void Add(long long &x,long long &y,long long a,long long b){//通分相加
    GCD=__gcd(y,b),LCM=y*b/GCD;//库里自带gcd，似乎比赛不能用
    x*=(LCM/y);
    a*=(LCM/b);
    y=LCM;
    x+=a;
    GCD=__gcd(x,y);
    x/=GCD;
    y/=GCD;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        Add(A,B,n,i);//A/B+n/i
    cout<<A/B;
    if(A%B){
        t=A/B;
        A-=B*t;
        cout<<"("<<A<<"/"<<B<<")";
    }
    return 0;
}