【解题报告】fzu 1753 Another Easy Problem - 求150个组合数的最大公约数

/*
	http://acm.fzu.edu.cn/problem.php?pid=1753
	fzu 1753 Another Easy Problem 
	求150个组合数（nCr(1 < n < 1e5 , 1 < r < 1e5)）的最大公约数
	解法：
	将一个组合数用大数表示法表示即 因子积的形式
	然后求出每一个因子在每个组合数表示中最少个数即为最大公约数的大数表示

*/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <ctime>
#include <cmath>
#define CLR(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;

const int inf = -(1<<30);
const int INF =  (1<<30);
const int N = 1e5 + 5;
int prime[N];

void Getprime(){
	bool p[N];CLR(p,1);
	p[0] = p[1] = 0;
	for(int i = 2 ; i < N ; i++){
		if(p[i])
			for(int j = i + i ; j < N ; j += i){
				if(p[i])
					p[j] = false;
			}
	}
	int cnt=0;
	for(int i = 0 ; i < N ; i++)
		if(p[i])
			prime[cnt++] = i;
}
int FacDivisor( int n , int div){
	// n! 有多少个div因子 存在sum里面
	int sum = 0;
	while( n ){
		sum += n/div;
		n /= div;
	}
	return sum;
}

int ComDivisor(int n,int r, int div){
	// nCr(n,r) 有多少个div因子 存在sum里面
	int sum = 0;
	sum = FacDivisor(n, div);
	sum -= FacDivisor(r, div);
	sum -= FacDivisor(n-r, div);
	return sum;
}

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	Getprime();
	int T;
	while(~scanf("%d",&T)){
		int g[N];CLR(g,0);
		int A[200],B[200];// nCr(Ai,Bi)
		int bound = INF;
		for(int i = 0 ; i < T ; i++){
			scanf("%d%d",&A[i],&B[i]);
			bound = min(A[i],bound);
		}
		ll ans = 1;
		for(int j = 0 ; prime[j] <= bound ; j++){ //遍历每一个素因子，取最小的
			g[j] = INF;
			for(int i = 0 ; i < T ; i++){
				int r = ComDivisor(A[i] , B[i] , prime[j]);
				g[j] = min(r , g[j]);
				//printf("n=%d r=%d prime[j]=%d g[%d]=%d\n", A[i], B[i], prime[j], j, g[j]);
			}
			for(int i = 0 ; i < g[j] ; i++)
				ans *= (ll) (prime[j]);
		}
		cout << ans << endl;
	}
	return 0;
}