程序员人生 网站导航

FZU 1753-Another Easy Problem(求多个组合数的最大公约数)

栏目:php教程时间:2015-05-29 08:28:09

 Another Easy Problem
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice FZU 1753
Appoint description: 

Description

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

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

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

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

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

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

小TT希望你告知他满足条件的最大的M

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

Input

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

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

Output

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

Sample Input

3100 150 160 1

Sample Output

10


思路:将每一个组合数化成质因子相乘的格式,然后找出所有组合数中该个质因子个数最小的,然后所有共同的质因子中个数最少的相乘,所得的结果就是组合数的最大公约数。

PS:WA了好几10遍,代码重新敲了N遍,结果把输出结果的printf改成了cout就对了,实在不知道为何,真是日了狗了。

#include <stdio.h> #include <math.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <sstream> #include <algorithm> #include <set> #include <queue> #include <stack> #include <map> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(⑴.0); #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 int prime[100010]={2,3,5}; int cnt[310][310]; int p[100010]; int k=3; struct node { int n,m; }q[210]; void is_prime() { int i,j; int flag=0; int gad=2; for(i=7; i<100010; i+=gad) { flag=0; gad=6-gad; for(j=0; prime[j]*prime[j]<=i; j++) { if(i%prime[j]==0) { flag=1; break; } } if(!flag) { prime[k++]=i; } } } int get(int n,int cc)//这个函数求的是n!中cc质因子的个数 { int cnt=0; while(n){ cnt+=n/cc; n=n/cc; } return cnt; } int get_res(int aa,int bb,int cc)//这个函数求的是C(n,m)中cc质因子的个数 { int sum=0; sum=get(aa,cc)-get(bb,cc)-get(aa-bb,cc); return sum; } int main() { int T; int i,j; LL ans; int minn; is_prime(); while(~scanf("%d",&T)){ ans=1; minn=inf; for(i=0;i<T;i++){ scanf("%d %d",&q[i].n,&q[i].m); minn=min(minn,q[i].n);//最大公约数的n值最大就是其中所有的n中最小的那个 } for(j=0;prime[j]<=minn;j++){//遍历每个素数因子,找最小的 p[j]=inf; for(i=0;i<T;i++){ int r=get_res(q[i].n,q[i].m,prime[j]); p[j]=min(r,p[j]); } for(i=0;i<p[j];i++) ans*=prime[j]; } cout<<ans<<endl; } return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐