fzu 1753 质因数的应用

Another Easy Problem

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

xtt最近学习了高斯消元法解方程组,现在他的问题来了，如果是以下的方程，那么应该如何解呢?

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

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

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

................

C(nk,mk)==0 (mod M)

xtt希望你告诉他满足条件的最大的M

其中C(i,j)表示组合数,例如C(5,2)=10,C(4,2)=6...

Input

输入数据包括多组，每组数据的第一行是一个正整数T(1<=T<=150)表示接下来描述的T个方程

接下来T行，每行包括2个正整数ni,mi (1<=mi<=ni<=100000)

Output

输出一行答案，表示满足方程组的最大M。

Sample Input

Sample Output

 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef __int64 LL;

 const int maxn=1e5+;

 int prime[],num,n[],m[];

 bool flag[maxn];

 void init()

 {

     memset(flag,true,sizeof(flag));

     int i,j;num=;

     for(i=;i<maxn;i++)

     {

         if(flag[i]) prime[num++]=i;

         for(j=;j<num&&i*prime[j]<maxn;j++)

         {

             flag[i*prime[j]]=false;

             if(i%prime[j]==) break;

         }

     }

 }

 int factor(int a,int b)

 {

     int sum=;

     while(b)

     {

         sum+=b/a;

         b/=a;

     }

     return sum;

 }

 int getfactor(int i,int j)

 {

     int sum=factor(prime[i],n[j]);

     sum-=factor(prime[i],m[j]);

     sum-=factor(prime[i],n[j]-m[j]);

     return sum;

 }

 LL mypow(LL a,LL b)

 {

     LL ret=;

     while(b)

     {

         if(b&) ret*=a;

         a*=a;

         b>>=;

     }

     return ret;

 }

 LL solve(int n,int MAX)

 {

     LL ans=;

     for(int i=;i<num&&prime[i]<=MAX;i++)

     {

         int min=,c;

         for(int j=;j<n;j++)

         {

             c=getfactor(i,j);

             min=min<c?min:c;

         }

         ans*=mypow(prime[i],min);

     }

     return ans;

 }

 int main()

 {

     init();

     int i,t,MIN;

     while(~scanf("%d",&t))

     {

         MIN=1e9;

         for(i=;i<t;i++)

         {

             scanf("%d %d",n+i,m+i);

             MIN=MIN<n[i]?MIN:n[i];

         }

         printf("%I64d\n",solve(t,MIN));

     }

     return ;

 }

巴特西

fzu 1753 质因数的应用

最新文章

热门文章