hdu 1099 Lottery，hdu1099lottery

hdu 1099 Lottery，hdu1099lottery

這是我第一次寫博客，作為一個ACMer，經常進別人的博客，所以自己也想寫寫博客。

HDU 1099

Lottery

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2648    Accepted Submission(s): 1191

Problem Description Eddy's company publishes a kind of lottery.This set of lottery which are numbered 1 to n, and a set of one of each is required for a prize .With one number per lottery, how many lottery on average are required to make a complete set of n coupons?  

 

Input Input consists of a sequence of lines each containing a single positive integer n, 1<=n<=22, giving the size of the set of coupons.  

 

Output For each input line, output the average number of lottery required to collect the complete set of n coupons. If the answer is an integer number, output the number. If the answer is not integer, then output the integer part of the answer followed by a space and then by the proper fraction in the format shown below. The fractional part should be irreducible. There should be no trailing spaces in any line of ouput.  

 

Sample Input 2 5 17  

 

Sample Output 3 5 11 -- 12 340463 58 ------ 720720

---

  題目的大概意思是說一套彩票有編號1到n共n種，張數不限，問你平均買多少張能把編號為1到n的n中彩票全買下來，也就是求期望。 舉個例子，當n=5時，第一張有用的概率為1，買一張就行了，第二張有用的概率為4/5，所以買5/4張彩票能買上對你有用的，一次類推，sum=1+5/4+5/3+5/2+5/1=11…5/12，再有就是注意格式 附上我的AC代碼

#include <iostream>
using namespace std;

int n,s,a1,b1,a2,b2,s1,s2;
int gcd(int x,int y)
{
    int t;
    while (x%y!=0)
    {
          t=x%y;
          x=y;
          y=t;
    }
    return y;
}
int f(int x,int y)
{
    int t1=a1,t2=b1;
    a1=t1*y+b1*x;
    b1=t2*y;
    int t=a1/b1;
    s+=t;
    a1-=t*b1;
    t=gcd(a1,b1);
    a1=a1/t;
    b1=b1/t;
}
int main()
{
    while (cin>>n)
    {
          s=0;
          a1=0;b1=1;
          for (int i=1;i<=n;i++)
          {
              f(n,i);
          }
          if (a1==0)
          cout <<s<<endl;//" "<<a1<<" "<<b1<<endl;
          else
          {
              int t1=0,t2=0,temp1=s,temp2=b1;
              while (temp1!=0)
              {
                  t1++;
                  temp1/=10;
              }
              t1++;
              while (temp2!=0)
              {
                  t2++;
                  temp2/=10;
              }
              for (int i=1;i<=t1;i++)
              cout <<" ";
              cout <<a1<<endl;
              cout <<s<<" ";
              for (int i=t2;i>=1;i--)
              cout <<"-";
              cout <<endl;
              for (int i=1;i<=t1;i++)
              cout <<" ";
              cout <<b1<<endl;
          }   
    }
    return 0;
}