SumyBlog

    n! 与组合数的素因子分解

    2013-10-13 算法 数论 算法 833 字 3 分钟

    阶乘和组合数的素因子分解不同于一般的素因子分解，不同之处就在于枚举的不是每个数的所有素因子，而是每个素因子包含哪些数。

    n!的素因子分解

    首先筛选出所有 [1,n] 的素数，然后对于一个素数 prime[i]，[1,n] 中有因子 prime[i] 的一定是形如：prime[i], 2 * prime[i] ,3 * prime[i] ,...第一轮我们得到的是 n/prime[i] 个因子，并且将 n 变成 n/prime[i]，这样一直到 n 等于 0 的时候就可以求出所有 n! 的 prime[i]的因子了。

    这里应用了递归思想：

    假设我们以 9! 求解 2 这个素因子的个数为例：

    含有2这个素因子的数字有：

    n - 因子个数
2 - 1
4 - 2
6 - 1
8 - 3

    计算过程：

    9/2=4 含2^1的数的个数
4/2=2 含2^2的数的个数
2/2=1 含2^3的数的个数

    核心思想是看 [2,n] 中含 m^t 次方的个数，含 m,m^2....., 有多少个加几。和就为最后的结果。

    贴个代码，不是我写的。。。

    #include<iostream>
using namespace std;
int main()
{
    int k,i,j,n,m,w,a;
    cin>>k;
    while(k--)
    {
        w=a=0;
        cin>>n>>m;
        w=0;
        do
        {
            n/=m;
            w+=n;
        }while(n);

        cout<<w<<endl;
    }
    return 0;
}

    组合数的素因子分解

    根据组合数公式 C(n,m)=n!/(n−m)!∗m!C( n , m ) = n! / ( n- m )! * m!

    可以将三个阶乘的素因子组合起来，个数进行加减运算（乘加除减）。具体的实现还是参照下面的题目吧。（太懒了，不想写了。。。）

    题目

    下面以FZU1753为例：

    这个题目是求解多个组合数公共素因子的个数，根据上面组合数分解的算法，就可以很容易写出来了。至于题目为什么要进行素因子分解，因为组合数太大了。

    还有题目需要进行一些优化。我们要求解 公共 因子的个数，所以只求出最小的那个组合数之间的公因子个数就行了，大于它的素数因子个数的求解就没有意义了。

    #include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

#define N 100000
bool flag[N+5]={0};
int prime[N],cnt=0;
void Prime(){  //筛素数
    for(int i=2;i<sqrt(N+1.0);i++){
        if(flag[i])
            continue;
        for(int j=2;j*i<=N;j++)
            flag[i*j]=true;
    }
    for(int i=2;i<=N;i++)
        if(!flag[i])
            prime[cnt++]=i;
}

int ans[N];
int tt[N];
int n;
int A[N],B[N];
void solve(int a,int b,int ab,int bound) //求a!/(b!*ab!)的素因子
{
    int tmp;
    for(int i=0;prime[i]<=bound;i++)
    {
        int c=0;
        if(prime[i]<=a)
        {
            tmp=a;
            while(tmp)
            {
                c+=tmp/prime[i];
                tmp/=prime[i];
            }
        }
        if(prime[i]<=b)
        {
            tmp=b;
            while(tmp)
            {
                c-=tmp/prime[i];
                tmp/=prime[i];
            }
        }
        if(prime[i]<=ab)
        {
            tmp=ab;
            while(tmp)
            {
                c-=tmp/prime[i];
                tmp/=prime[i];
            }
        }
        tt[i]=c;
    }
}
int main()
{
    Prime();
    while(scanf("%d",&n)!=EOF)
    {
        memset(ans,0x3f,sizeof(ans));
        int minnum=1000000;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&A[i],&B[i]);
            minnum=min(A[i],minnum);
        }
        for(int i=0;i<n;i++)
        {
            memset(tt,0,sizeof(tt));
            solve(A[i],B[i],A[i]-B[i],minnum);
            for(int i=0;prime[i]<=minnum;i++)
            {
                ans[i]=min(ans[i],tt[i]);
            }
        }
        long long result=1;
        for(int i=0;prime[i]<=minnum;i++)
        {
            result*=(long long)(pow(1.0*prime[i],ans[i]));
        }
        printf("%I64d\n",result);
    }
    return 0;
}

    参考内容

    上一篇数组中只出现过一次的元素
    下一篇ACM计算几何题目推荐及做题统计