Fork me on GitHub

[UVa-10375] Choose and divide

发表于 | 分类于
字数统计: 368字 | 阅读时长 ≈ 2分钟

题面

传送门:UVa-10375
题目大意:给出p,q,r,s,求出C(p,q)/C(r,s)的值,其中p,q,r,s∈[1,10000]；且p >= q,r >= s;

样例

Sample Input
10 5 14 9
93 45 84 59
145 95 143 92
995 487 996 488
2000 1000 1999 999
9998 4999 9996 4998
Sample Output
0.12587
505606.46055
1.28223
0.48996
2.00000
3.99960

思路

先预处理1W以内的质数集合prime[],
然后唯一分解定理,用pf[i]记录每个质数要乘或者除的个数,最后pow一遍即可.

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10001;

int prime[maxn],cnt = 0,pf[maxn];
bool is_prime[maxn];

void Euler_Prime(int x)
{
	memset(is_prime,1,sizeof(is_prime));
	is_prime[1] = 0;
	for (int i = 2; i <= x; i++)
	{
		if (is_prime[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && i *prime[j] <= x; j++)
		{
			is_prime[i*prime[j]] = 0;
			if (i % prime[j] == 0) break;
		}
	}
}
void work(int n,int d)
{
	for (int i = 1; i <= cnt; i++)
	{
		while(n % prime[i] == 0)
		{
			n /= prime[i];
			pf[i] += d;		
		}
		if (n == 1) break;
	}
}
void update(int n,int d)
{
	for (int q = 1; q <= n; q++)
		work(q,d);
}
int main(int argc, char *argv[])
{
	Euler_Prime(10000);
	int p,q,r,s;
	while(scanf("%d %d %d %d",&p,&q,&r,&s) == 4)
	{
		double ans = 1.0;
		memset(pf,0,sizeof(pf));
		update(p,1); update(q,-1);update(p-q,-1);
		update(r,-1);update(s,1); update(r-s,1);
		for (int i = 1; i <= cnt; i++)
		ans *= pow(prime[i],pf[i]);
		printf("%.5lf\n",ans);
	}
	return 0;
}