# Lottery

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

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

Author

eddy

Recommend

JGShining

sum=n*∑(1/i);----->n*(1+1/2+1/3+.....+1/n);

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 using namespace std;
6 int gcd(_int64 a,_int64 b)
7 {
8     if(b==0)
9         return a;
10     gcd(b,a%b);
11 };
12
13 void swap(_int64 *a,_int64 *b)
14 {
15     *a^=*b,
16     *b^=*a,
17     *a^=*b;
18 }
19 int main()
20 {
21     int n,i;
22     char str[20]={'\0'},num[20]={'\0'};
23     _int64 a,b,c,real;
24     while(scanf("%d",&n)!=EOF)
25     {
26         a=b=1;
27         for(i=2;i<=n;i++)
28         {
29             a=a*i+b;
30             b*=i;
31          if(a<b) swap(a,b);
32            c=gcd(a,b);
33            a/=c;
34            b/=c;
35         }
36     if((n*a)%b)
37     {
38        real=(a/b)*n;
39           a%=b;
40           a*=n;
41         real+=a/b;
42            a%=b;
43          c=gcd(a,b);
44           a/=c;
45           b/=c;
46     itoa(b,str,10);
47     itoa(real,num,10);
48     for(i=0;i<=strlen(num);i++)
49         printf(" ");
50         printf("%I64d\n%I64d ",a,real);
51     for(i=0;i<strlen(str);i++)
52         printf("-");
53         puts("");
54     for(i=0;i<=strlen(num);i++)
55         printf(" ");
56         printf("%I64d\n",b);
57     }
58     else
59         printf("%I64d\n",n*a/b);
60     }
61     return 0;
62 }```

657 篇文章64 人订阅

0 条评论

## 相关文章

### hdu-----(1507)Uncle Tom's Inherited Land*(二分匹配)

Uncle Tom's Inherited Land* Time Limit: 2000/1000 MS (Java/Others)    Memory Lim...

25840

40150

### hdu----(5055)Bob and math problem(贪心)

Bob and math problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 327...

29450

### HDU 1004 Let the Balloon Rise【STL<map>】

Let the Balloon Rise Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 655...

30240

### HDUOJ--------A simple stone game（尼姆博弈扩展)(2008北京现场赛A题）

A simple stone game                                                             ...

29050

### HDUOJ-----1066Last non-zero Digit in N!

Last non-zero Digit in N! Time Limit: 2000/1000 MS (Java/Others)    Memory Limit...

33960

### HDU 1103 Flo's Restaurant(模拟+优先队列)

Flo's Restaurant Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/...

28860

### poj----Ubiquitous Religions

Ubiquitous Religions Time Limit: 5000MS Memory Limit: 65536K Total Submi...

37060

### HDU 3367 Pseudoforest(Kruskal)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/655...

30850

### POJ-1276-Cash Machine（多重背包）

Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

29140