FZU 1753-Another Easy Problem(求多個組合數的最大公約數)
來源：程序員人生 發布時間：2015-05-29 08:28:09 閱讀次數：3677次
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)
思路：將每一個組合數化成質因子相乘的格式，然后找出所有組合數中該個質因子個數最小的，然后所有共同的質因子中個數最少的相乘，所得的結果就是組合數的最大公約數。
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
