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

spoiler posted @ 2011年5月05日 02:14 in 数论 , 1704 阅读

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

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;
}