1099 Lottery

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1099

英文水平太差了，题目实在是不知道是什么意思，然后看了其他高手写的思路，才看明白。

题意，收集n张彩票（1~n）平均需要抽几次彩票。这相当于是概率的问题。

假设n=3；

收集1 2 3 有如下过程

第一次抽到的概率为 1　　   抽到平均需要1次

第二次抽到的概率为2/3 　　抽到平均需要2/3次

第三词抽到的概率为1/3　　 抽到的平均需要3/1次

so 平均需要 1+2/3+3/1=5.5次

 #include <stdio.h>

 #include <iostream>

 #include <string>

 #include <cstring>

 using namespace std;

 __int64 gcd(__int64 a, __int64 b)//求最小公倍数

 {

     if(b == ) return a;

     return gcd(b, a % b);

 }

 __int64 getlen(__int64 x)//求位数

 {

     __int64 cnt = ;

     while(x)

     {

         cnt++;

         x /= ;

     }

     return cnt;

 }

 int main()

 {

     __int64 n;

     while(scanf("%I64d", &n) != EOF)

     {

         __int64 fm = , fz = n, temp;//fz分子 fm分母；

         for(__int64 i = ; i <= n; i++)

         {

             fz = fz * i + fm * n;//分子 分母交叉相乘 eg:3/1+3/2=(/2*3+1*3)/1*2=9/2;

             fm *= i;

             temp = gcd(fz, fm);

             fz /= temp;

             fm /= temp;

         }

         __int64 a = fz / fm;

         if(fz % fm == )

         {

             printf("%I64d\n", a);

             continue;

         }

         fz = fz - fm * a;

         //计算位数

         __int64 len_fm = getlen(fm);//经过上面的化简必然是分子小于分母

         // __int64 len_fz = getlen(fz);

         __int64 len_a = getlen(a);

         // __int64 maxx = max(len_fm, len_fz);

         for(__int64 i = ; i < len_a + ; i++)

             putchar(' ');

         printf("%I64d\n", fz);

         printf("%I64d ", a);

         for(__int64 i = ; i < len_fm; i++)

             putchar('-');

         puts("");

         for(__int64 i = ; i < len_a + ; i++)

             putchar(' ');

         printf("%I64d\n", fm);

     }

     return ;

 }