FZU1753 Another Easy Problem【组合数】

本文主要是介绍FZU1753 Another Easy Problem【组合数】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://acm.fzu.edu.cn/problem.php?pid=1753

题目大意：

给你 T 个组合数 C(N，K)，求这 T 个组合数的最大公约数。

解题思路：

将组合数用 素因子分解的形式来表示。然后求出每个素因子在公约数中最小的阶，

相乘得到答案。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;
const int MAXN = 100000;
const int INF = 0x3f3f3f;bool Prime[MAXN+10];
int Primer[MAXN+10];int GetPrime()
{for(int i = 2; i <= MAXN; ++i)Prime[i] = true;for(int i = 2; i <= MAXN; ++i){if(Prime[i]){for(int j = i+i; j <= MAXN; j+=i)Prime[j] = false;}}int num = 0;for(int i = 2; i <= MAXN; ++i)if(Prime[i])Primer[num++] = i;return num;
}int Fun(int n,int div)
{int sum = 0;while(n){sum += n/div;n /= div;}return sum;
}int Solve(int n,int r,int div)
{int sum = 0;sum = Fun(n,div);sum -= Fun(r,div);sum -= Fun(n-r,div);return sum;
}
int A[220],B[220],G[220];
int main()
{int num = GetPrime();int T;while(~scanf("%d",&T)){for(int i = 0; i < T; ++i)scanf("%d%d",&A[i],&B[i]);int Min = INF;for(int i = 0; i < T; ++i)Min = min(A[i],Min);LL ans = 1;for(int i = 0; Primer[i] <= Min; ++i){G[i] = INF;for(int j = 0; j < T; ++j){int temp = Solve(A[j],B[j],Primer[i]);G[i] = min(G[i],temp);}for(int j = 0; j < G[i]; ++j)ans *= (LL)Primer[i];}printf("%I64d\n",ans);}return 0;
}

这篇关于FZU1753 Another Easy Problem【组合数】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---