HDUOJ 1099——Lottery

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

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

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

25840
来自专栏杨熹的专栏

【LEETCODE】模拟面试-357- Count Numbers with Unique Digits

题目: https://leetcode.com/problems/count-numbers-with-unique-digits/ Given a non...

40150
来自专栏ml

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
来自专栏ml

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

A simple stone game                                                             ...

29050
来自专栏ml

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
来自专栏ml

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

扫码关注云+社区

领取腾讯云代金券