紫书例题10-3 选择与除法 Choose and divide（UVA10375）

题意：给出p,q,r,s计算C(p,q)/C(r,s) 范围是10000. 分析：暴力计算组合数是不可取的，因为有阶乘的存在。那么该怎么办呢？做除法实际上就是约去一些相同的因子，这些因子可以由唯一分解得到。想到这，结果已经是很显然了，简单地对式子进行推导，计算每一项对总的质因子贡献，得到每一个素数prime[i]对应的指数e[i],相乘即可得出答案。 分子为+1，分母当然就是-1的贡献。唯一分解题… 代码：

#include
using namespace std;
const int maxn  =1e5+2;
bool vis[maxn];int prime[maxn];int cnt=0;
int e[maxn];
void pre(int n){
	memset(vis,0,sizeof(vis));memset(e,0,sizeof(e));
	for(int i=2;i