紫书例题 10-17 UVa 1639（数学期望+分数处理+处理溢出）

设当前有k个，那么也就是说拿到其他图案的可能是（n-k）/n

那么要拿到一个就要拿n/（n-k）次

所以答案就是n（1/n + 1/(n-1) ......1/2 + 1 / 1）

看起来很简单，但是实现有很多细节

一开始我是写了一个分数加法的函数

然后发现中间过程会溢出

所以要做两个操作

（1）分母为1和n不算，最后算整数部分再加上去

因为如果算的话就要乘进去，分母会溢出

（2）要直接算所有数的最小公倍数，然后分子一起加（看代码）

我一开始是单独一个个分数来加减，这样在算分子的时候中间结果会溢出

#include<cstdio>

#include<cmath>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

int n;

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int get_len(ll x)

{

	int ret = 0;

	while(x)

	{

		ret++;

		x /= 10;

	}

	return ret;

}

void print(ll x, ll a, ll b)

{

	if(a == 0)

	{

		printf("%lld\n", x);

		return;

	}

	REP(i, 0, get_len(x) + 1) putchar(' '); printf("%lld\n", a);

	printf("%lld ", x); REP(i, 0, get_len(b)) putchar('-'); puts("");

	REP(i, 0, get_len(x) + 1) putchar(' '); printf("%lld\n", b);

}

int main()

{

	while(~scanf("%d", &n))

	{

		if(n == 1) { puts("1"); continue; }

		ll x = 1;

		REP(i, 2, n)

			x = lcm(x, i);

		ll a = 0, b = x;

		REP(i, 2, n) a += x / i;

		a *= n;

		ll t = gcd(a, b);

		a /= t, b /= t;

		print(1 + n + a / b, a % b, b);

	}

	return 0;

}

巴特西

紫书例题 10-17 UVa 1639（数学期望+分数处理+处理溢出）

最新文章

热门文章

巴特西

紫书 例题 10-17 UVa 1639（数学期望+分数处理+处理溢出）

最新文章

热门文章

紫书例题 10-17 UVa 1639（数学期望+分数处理+处理溢出）