Choose and divide

Voj

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string.h>
using namespace std;

const int MAXN = 10000;
//素数表
vector<int> PrimerTable;

//计算答案的唯一分解定理中第i个素数有几个
int PrimeFactor[1230];

void InitPrimerTable() {
	bool IsNotP[10001];
	memset(IsNotP, false, sizeof(IsNotP));
	for (int i = 2; i <= MAXN; ++i) {
		for (int j = i << 1; j <= MAXN; j += i) {
			IsNotP[j] = true;
		}
	}
	for (int i = 2; i <= MAXN; ++i) {
		if (IsNotP[i] == false) {
			PrimerTable.push_back(i);
		}
	}
}

int p, q, r, s;

//求n^d
void AddPerFactor(int n, const int& d) {
	for (int i = 0; i < PrimerTable.size(); ++i) {
		while (n % PrimerTable[i] == 0) {
			n /= PrimerTable[i];
			PrimeFactor[i] += d;
		}
	}
}

//求(n!)^d
void AddToFactor(const int& n, const int& d) {
	for (int i = 1; i <= n; ++i) {
		AddPerFactor(i, d);
	}
}

//求C(p,q)/C(r,s)
void AddAllFactor() {
	AddToFactor(p, 1);
	AddToFactor(r - s, 1);
	AddToFactor(s, 1);
	AddToFactor(p - q, -1);
	AddToFactor(q, -1);
	AddToFactor(r, -1);
}

//a^b，注意有负数
double QPower(int a, int b) {
	double Ans = 1;
	bool IsPositive = true;
	if (b < 0) {
		b *= -1;
		IsPositive = false;
	}
	while (b > 0) {
		if (b & 1) {
			Ans *= a;
		}
		a *= a;
		b >>= 1;
	}
	return IsPositive ? Ans : 1 / Ans;
}

double PrimeFactorToAns() {
	double Ans = 1.;
	for (int i = 0; i < PrimerTable.size(); ++i) {
		Ans *= QPower(PrimerTable[i], PrimeFactor[i]);
	}
	return Ans;
}

int main(){
	InitPrimerTable();
	while (cin >> p >> q >> r >> s) {
		memset(PrimeFactor, 0, sizeof(PrimeFactor));
		AddAllFactor();
		printf("%.5lf\n", PrimeFactorToAns());
	}
	return 0;

}