2013
11-27

# 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

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;
}