UVA 10288 Coupons---概率 && 分数类模板

题目链接：

https://cn.vjudge.net/problem/UVA-10288

题目大意：

一种刮刮卡一共有n种图案，每张可刮出一个图案，收集n种就有奖，问平均情况下买多少张才能中奖？用最简的分数形式表示答案。n<=33。

解题思路：

假设现在已刮到k个图案了，刮到新图案的概率是(n-k)/n，即若要再收集一个新图案平均要刮s=n/(n-k)次。所以只需要穷举k=1 to n，累加s的和就行了。注意式子可以将分子n提取出来。

先附上分数类模板

 1 struct Fraction//分数类
 2 {
 3     ll num, den;//num为分子，den为分母
 4     Fraction(ll num = 0, ll den =  1)
 5     {
 6         if(den < 0)
 7         {
 8             num = -num;
 9             den = -den;
10         }
11         assert(den != 0);//den=0程序终止
12         ll g = __gcd(abs(num), den);
13         this->num = num / g;
14         this->den = den / g;
15     }
16     Fraction operator + (const Fraction& o)const
17     {
18         return Fraction(num * o.den + den * o.num, den * o.den);
19     }
20     Fraction operator - (const Fraction& o)const
21     {
22         return Fraction(num * o.den - den * o.num, den * o.den);
23     }
24     Fraction operator * (const Fraction& o)const
25     {
26         return Fraction(num * o.num, den * o.den);
27     }
28     Fraction operator / (const Fraction& o)const
29     {
30         return Fraction(num * o.den, den * o.num);
31     }
32     bool operator < (const Fraction& o)const
33     {
34         return num * o.den < den * o.num;
35     }
36     bool operator == (const Fraction& o)const
37     {
38         return num * o.den == den * o.num;
39     }
40 };

注意输出格式（很伤）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 struct Fraction//分数类
 5 {
 6     ll num, den;//num为分子，den为分母
 7     Fraction(ll num = 0, ll den =  1)
 8     {
 9         if(den < 0)
10         {
11             num = -num;
12             den = -den;
13         }
14         assert(den != 0);//den=0程序终止
15         ll g = __gcd(abs(num), den);
16         this->num = num / g;
17         this->den = den / g;
18     }
19     Fraction operator + (const Fraction& o)const
20     {
21         return Fraction(num * o.den + den * o.num, den * o.den);
22     }
23     Fraction operator - (const Fraction& o)const
24     {
25         return Fraction(num * o.den - den * o.num, den * o.den);
26     }
27     Fraction operator * (const Fraction& o)const
28     {
29         return Fraction(num * o.num, den * o.den);
30     }
31     Fraction operator / (const Fraction& o)const
32     {
33         return Fraction(num * o.den, den * o.num);
34     }
35     bool operator < (const Fraction& o)const
36     {
37         return num * o.den < den * o.num;
38     }
39     bool operator == (const Fraction& o)const
40     {
41         return num * o.den == den * o.num;
42     }
43 };
44 int main()
45 {
46     ll n, k, ans, cases = 0;
47     while(cin >> n)
48     {
49         Fraction ans;
50         for(int i = 1; i <= n; i++)
51         {
52             ans = ans + Fraction(n, i);
53         }
54         ll t = ans.num / ans.den;
55         ans.num -= t * ans.den;
56         if(ans.num == 0)
57         {
58             cout<<t<<endl;
59         }
60         else
61         {
62             string s;
63             stringstream ss, ss1;
64             ss << t;
65             ss >> s;
66             int kongge = s.size();
67             for(int i = 0; i <= kongge; i++)cout<<" ";
68             cout<<ans.num<<"
";
69 
70             ss1 << ans.den;
71             ss1 >> s;
72             int duanxian = s.size();
73             cout<<t<<" ";
74             for(int i = 0; i < duanxian; i++)cout<<"-";
75             cout<<"
";
76             for(int i = 0; i <= kongge; i++)cout<<" ";
77             cout<<ans.den<<"
";
78         }
79     }
80     return 0;
81 }