Another Easy Problem FZU - 1753唯一分解定理

题目链接

题目

---

小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

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

Output

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

Sample Input

3
100 1
50 1
60 1

Sample Output

10

---

题意:

中文题, 题意清晰.

思路:

当然这题不会是高斯消元, 大概就是唯一分解定理, 然后就是求阶乘的分解形式,根据具体数学, 具体如何分解看我代码吧

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 1000000 + 10;
int pri[maxn];
int a[maxn];
int b[maxn];
bool vis[maxn];
int m[200],n[200];
int num;

void prime(){
    num = 0;
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    for(int i = 2; i < maxn; ++i){
        if (!vis[i]) pri[++num] = i;
        for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
            vis[ i* pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

int solve(int n, int t){//求阶乘中有多少个某个素数
   int ans = 0;
   int x = t;
   while(t <= n){
         ans += n / t;
         t *= x;
   }return ans;
}

LL qpow(LL x, LL n){
    LL ans = 1;
    while(n){
        if (n&1) ans *= x;
        x *= x;
        n >>= 1;
    }return ans;
}

int main(){
    prime();
    int t;
    while(scanf("%d", &t) != EOF){
        int minx = INF;
        for(int i = 1; i <= t; ++i){
            scanf("%d %d", &n[i], &m[i]);
            minx = min( minx, n[i]);
        }fill(a, a + maxn, INF);
        for(int j = 1; j <= t; ++j)
            for(int i = 1; i <= num &&  pri[i] <= minx; ++i)
            a[pri[i]] = min(a[pri[i]],solve(n[j], pri[i])  - solve(m[j], pri[i]) - solve(n[j] - m[j], pri[i]));
        LL ans = 1;
        for(int i = 1; i < maxn; ++i){
            if(a[i] != INF)
                ans *= qpow(i, a[i]);
        }
     printf("%I64d\n",ans);
  // cout<<ans<<endl;
    }return 0;
}