首页 > ACM题库 > HDU-杭电 > HDU 1099 Lottery -模拟-[解题报告] C++
2013
11-27

HDU 1099 Lottery -模拟-[解题报告] C++

Lottery

问题描述 :

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 consists of a sequence of lines each containing a single positive integer n, 1<=n<=22, giving the size of the set of coupons.

输出:

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.

样例输入:

2
5
17

样例输出:

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

题目有点难懂,直接看样例又不太直观。不管了。其实题意很简单,实际上就是一道数学题+编码

题意:求一个数x的f(x)=x*(1/1+1/2+···+1/x),并按照有分数是输出其带分数的形式。注意格式输出。

1.一开始做了溢出了,仔细看看才知道__int64貌似也不兼容22!的大小,一开始用数组记录22!的阶乘的方法不行。

2.方法很多,这里采用的是模拟手工暴力运算,先将x乘进到括号里的分数,然后相加。相加的时候将分母扩大到最小公倍数,分子相应增大,以此类推

 

#include <stdio.h>
 #include <algorithm>
 using namespace std;
 #include <iostream>
 
 __int64 gcd(__int64 x1,__int64 x2){
     return x2 ? gcd(x2,x1%x2) : x1;
 }
 __int64 lcm(__int64 x1,__int64 x2){
     return x1 / gcd(x1,x2) * x2;
 }
 int getl(__int64 x){
     int cnt = 0;
     while(x>0){
         cnt++;x/=10;
     }
     return cnt;
 }
 void cal(int x)
 {
     int cnt = 0;
     __int64 fz=x,fm=1,tx;
     for(int i=2;i<=x;i++)
     {
         tx = lcm(fm,i);
         fz *= (tx/fm);
         fz += (tx/i*x);
         fm = tx;
         if(fz > fm) cnt+=(fz/fm) , fz %= fm;
         tx = gcd(fz,fm);
         fz /= tx;
         fm /= tx;
     }
     fz %= fm;
     //cout<<cnt<<' ' <<fz<<' '<<fm<<'\n';
     if(fz == 0) cout<<cnt<<endl;
     else
     {
         int l1 = getl(cnt),l2 = getl(fm);
         for(int i=0;i<=l1;i++) cout<<' ';
         cout<<fz<<'\n';
         cout<<cnt<<' ';
         for(int i=0;i<l2;i++) cout<<'-';
         cout<<'\n';
         for(int i=0;i<=l1;i++) cout<<' ';
         cout<<fm<<'\n';
     }
 }
 
 int main()
 {
     int n;
     while(cin>>n)
     {
         if(n==1) cout<<"1\n";
         else cal(n);
     }
     return 0;
 }