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

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这个素因子的数字有:

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

计算过程:

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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!/(nm)!m!C( n , m ) = n! / ( n- m )! * m!

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

题目

下面以FZU1753为例:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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;
}

参考文献