首页 > 代码库 > fzu 1753 质因数的应用

fzu 1753 质因数的应用

2024-07-12 12:19:37   218人阅读

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

3100 150 160 1

Sample Output

10

 

 1 #include <iostream> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 typedef __int64 LL; 8 const int maxn=1e5+5; 9 int prime[10000],num,n[200],m[200];10 bool flag[maxn];11 12 void init()13 {14     memset(flag,true,sizeof(flag));15     int i,j;num=0;16     for(i=2;i<maxn;i++)17     {18         if(flag[i]) prime[num++]=i;19         for(j=0;j<num&&i*prime[j]<maxn;j++)20         {21             flag[i*prime[j]]=false;22             if(i%prime[j]==0) break;23         }24     }25 }26 27 int factor(int a,int b)28 {29     int sum=0;30     while(b)31     {32         sum+=b/a;33         b/=a;34     }35     return sum;36 }37 38 int getfactor(int i,int j)39 {40     int sum=factor(prime[i],n[j]);41     sum-=factor(prime[i],m[j]);42     sum-=factor(prime[i],n[j]-m[j]);43     return sum;44 }45 46 LL mypow(LL a,LL b)47 {48     LL ret=1;49     while(b)50     {51         if(b&1) ret*=a;52         a*=a;53         b>>=1;54     }55     return ret;56 }57 58 LL solve(int n,int MAX)59 {60     LL ans=1;61     for(int i=0;i<num&&prime[i]<=MAX;i++)62     {63         int min=10000,c;64         for(int j=0;j<n;j++)65         {66             c=getfactor(i,j);67             min=min<c?min:c;68         }69         ans*=mypow(prime[i],min);70     }71     return ans;72 }73 74 int main()75 {76     init();77     int i,t,MIN;78     while(~scanf("%d",&t))79     {80         MIN=1e9;81         for(i=0;i<t;i++)82         {83             scanf("%d %d",n+i,m+i);84             MIN=MIN<n[i]?MIN:n[i];85         }86         printf("%I64d\n",solve(t,MIN));87     }88     return 0;89 }

 


联系
我们