FOJ（1753 Another Easy Problem 又一种整数分解）

题目大意：就是给你多个组合数，让你求出

C(n1,m1)==0 (mod M)

C(n2,m2)==0 (mod M)

C(n3,m3)==0 (mod M)

的最大的M满足上式，

题目分析：

其实就是把这些组合数，分解成素数因子，然后求每个因子出现的最少的次数，题目不难 但时间卡的好紧，我超时得想吐，如果您也遇到跟我一样的情况，请你细细看我 代码提示的各个优化环节！不懂的 留言，我们一起讨论

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[1000011];
bool flag[1000001];
int sim[1000001];
int num1[151],num2[151];
int cnt;
void get_pri(){//生成素数表
	for(int i=1;i<=1000000;i++)
		flag[i]=true;
	pri[1]=2;
	cnt=1;
	flag[0]=flag[1]=false;
	for(int i=4;i<=1000000;i+=2)
		flag[i]=false;
	for(int i=3;i<3000;i+=2)
		for(int j=i*i;j<=1000000;j+=2*i)
			flag[j]=false;
	for(int i=3;i<=1000000;i+=2)
		if(flag[i])
			pri[++cnt]=i;
	return ;
}
int paw(int a,int t){
	int ans=1;
	while(t){
		if(t%2==1)
			ans=ans*a;
		a=a*a;
		t/=2;
	}
	return ans;
}
void solve(){
	int cas,n,k,i,s,j,t;
	bool flag;
	int maxn;
	while(scanf("%d",&cas)!=EOF){
		flag=false;
		maxn=0;
		for(i=1;i<=cas;i++){
			scanf("%d %d",&num1[i],&num2[i]);
			if(maxn<num1[i])
				maxn=num1[i];
			if(num1[i]==num2[i])
				flag=true;
                         //如果哦值为1的情况，就不用计算了，肯定就是1啦！
		}
		if(flag){
			printf("1\n");
			continue;
		}
		for(j=0;j<=100000;j++)
			sim[j]=2147483647;
		for(t=0;t<cas;t++){
			n=num1[t+1];
			k=num2[t+1];
			for(i=1;i<=cnt&&pri[i]<=maxn;i++){
				if(sim[i]==0)//这也是一个优化的地方，如果是0，
                                       //这个素数在各个组合数里出现的最少次数肯定是0啦
					continue;
				int sum=0;
				int p=pri[i];
				while(n>=p){//这个就是计算各个素数在组合数里出现的次数
					sum=sum+n/p-k/p-(n-k)/p;
					p*=pri[i];
                                  //记得一次把这个写错了写成“p*=p”悲剧哦，段错误，肯定超出int范围啦！
				}
				if(sum<sim[i])
					sim[i]=sum;
                             //sim[i]是记录第i个素数在各个组合数里出现的最少的素数！
			}	
		}
		long long ans=1;
                 //下面这个循环就无非是 计算每个组合数里，各个素数出现的最少次数，
               //组合成的数ans，也就是题目要求的数！
		for(i=1;i<=cnt&&pri[i]<=maxn;i++){
			if(sim[i]>0&&sim[i]!=2147483647){
				ans=ans*paw(pri[i],sim[i]);
			}
		}
		printf("%lld\n",ans);
	}
	return ;
}
int main(){
	get_pri();
	solve();
	return 0;
}