题目
题目大意
大街上到处在卖彩票, 一元钱一张。购买撕开它上面的锡箔,
你会看到一个漂亮的图案。图案有\(n\)种,
如果你收集到所有\(n\)(\(n ≤ 33\))种彩票, 就可以得到大奖。请问,
在平均情况下, 需要买多少张彩票才能得到大奖呢? 如\(n = 5\)时的答案为\(11\frac{5}{12}\)。
题解
设已经有\(k\)个图案: 平均拿\(\frac{n}{n - k}\)次就可多搜集一个,
所以总次数为: \[n\sum_{i = 0}^{n -
1}\frac{1}{n - i}\]
然后再用个分数类就可以了。
此处再说一个奇妙的事情,
我如果用自己写的GreatestCommonDivisor函数会\(WA\), 但是如果用\(C++\)函数库里的__gcd就能\(AC\), 至今不能理解。
还有输出最好不要重载输出流<<运算符, 容易\(RE\)。
另外此题可打表。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
using namespace std;
struct Fraction {
long long numerator, denominator;
Fraction(register long long knum = 0, register long long kden = 1) {
if (kden < 0) {
knum = -knum;
kden = -kden;
}
assert(kden != 0);
register long long g(__gcd((long long)abs(knum), kden));
this->numerator = knum / g;
this->denominator = kden / g;
}
inline Fraction operator +(const Fraction& o) const {
return Fraction(numerator * o.denominator + denominator * o.numerator, denominator * o.denominator);
}
inline Fraction operator -(const Fraction& o) const {
return Fraction(numerator * o.denominator - denominator * o.numerator, denominator * o.denominator);
}
inline Fraction operator *(const Fraction& o) const {
return Fraction(numerator * o.numerator, denominator * o.denominator);
}
inline Fraction operator /(const Fraction& o) const {
return Fraction(numerator * o.denominator, denominator * o.numerator);
}
bool operator <(const Fraction& o) const {
return numerator * o.denominator < denominator * o.numerator;
}
bool operator ==(const Fraction& o) const {
return numerator * o.denominator == denominator * o.numerator;
}
};
int main(int argc, char const *argv[]) {
register long long n, k, ans, cases(0);
while (~scanf("%lld", &n)) {
register Fraction ans;
for (register int i(1); i <= n; ++i) {
ans = ans + Fraction(n, i);
}
register long long t(ans.numerator / ans.denominator);
ans.numerator -= t * ans.denominator;
if (!ans.numerator) {
printf("%lld\n", t);
} else {
register string s;
register stringstream ss1, ss2;
ss1 << t;
ss1 >> s;
register int space(s.size());
for (register int i(0); i <= space; ++i) putchar(' ');
printf("%lld\n", ans.numerator);
ss2 << ans.denominator;
ss2 >> s;
register int line(s.size());
printf("%lld ", t);
for (register int i(0); i < line; ++i) putchar('-');
putchar('\n');
for (register int i(0); i <= space; ++i) putchar(' ');
printf("%lld\n", ans.denominator);
}
}
return 0;
}
|