题目描述

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

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

输入输出格式

输入格式：

整数n（2≤n≤33），表示不同球星名字的个数。

输出格式：

输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为（复制到记事本）：

3 5-- 20 第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。

分数必须是不可约的。

输入输出样例

输入样例#1：

2

输出样例#1：

3 设f[i]为剩下i个球星的期望 f[i]=(i/n)f[i+1]+((n-i)/n)f[i]+1 移项： (i/n)f[i]=(i/n)f[i+1]+1 f[i]=f[i+1]+n/i 所以答案就是n∑(1/i)

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               5 #include
              
                6 using namespace std; 7 typedef long long lol; 8 lol n,p,q,r; 9 lol gcd(lol a,lol b)10 {11   if (!b) return a;12   return gcd(b,a%b);13 }14 int get_num(lol a)15 {16   int cnt=0;17   while (a)18     {19       a/=10;20       cnt++;21     }22   return cnt;23 }24 int main()25 {lol i;26   cin>>n;27   p=0;q=1;28   for (i=1;i<=n;i++)29     {30       p=p*i+q*n;31       q=q*i;32       r=gcd(p,q);33       p/=r;34       q/=r;35     }36   int r=p/q;37   p%=q;38   if (p==0)39     printf("%d\n",r);40   else41     {42       int s=get_num(r);43       int s1=get_num(p),s2=get_num(q);44       for (i=1;i<=s;i++)45         cout<<' ';46       cout<
               
<