由于唯一分解的题目很多,所有从数论独立出来

唯一分解定理

$$\begin{align}
&N=p_1^{e_1}p_2^{e_2}…p_m^{e_m} \\
&gcd(a,b)=p_1^{min(e_{a_1},e_{b_1})}p_2^{min(e_{a_2},e_{b_2})}…p_m^{min(e_{a_m},e_{b_m})} \\
&lcm(a,b)=p_1^{max(e_{a_1},e_{b_1})}p_2^{max(e_{a_2},e_{b_2})}…p_m^{max(e_{a_m},e_{b_m})} \\
&lcm(a,b)=ab/gcd(a,b)
\end{align}
$$

因数分解

因子个数

$\prod (e_i + 1)$

因子的和

$$sum_n=\prod_1^k \sum_0^{e_i}p_i^j$$

即每个质因子贡献一部分。质因数分解后分别用进行等比数列求和即可。
其中求和较小时可以直接套公式$\sum_0^{n}{a_n}=\frac{q_{n+1}-a_0}{q-1}$,而如果取模则可以进行等比数列二分求和。

1
2
3
4
5
6
7
8
9
10
11
12
LL sum(LL a, LL n)
{
LL res = 1, tmp = 1;
while(n)
{
if(n&1) res = (res * a + tmp) % mod;
tmp = tmp * (1 + a) % mod;
a = a * a % mod;
n >>= 1;
}
return ans;
}

求多个数因子的和时可以用筛法预处理

$$\begin{cases}
sum_n = n+1 &n为素数 \\
sum_n = (1 + p + p^2 + … + p^e)*sum_m & n = p^e*m
\end{cases}
$$

n!的质因数分解

n!的最多可以分解为某个因子p的次数
$e(p)=n/p^1+n/p^2+…n/p^k \;\; p^k \leq n < p^{k+1}$
即<n的数每p个会提供一个因数p,每p^2个多提供一个因数p,以此类推

1
2
3
4
5
6
7
8
9
int e(int n,int p)
{
int res=0;
while(n){
r+=n/p;
n/=p;
}
return res;
}
  • 阶乘末尾0的个数:即 e(5)
    因为2*5=10,n!中因子2的个数比5的多,因此因子中有e(5)个10

求n!质因子个数的和

同样可以用筛法预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define N 1000000
const int maxn=1000010;
int t=N,res[maxn],vis[maxn];
void init(){
memsest(vis,0,sizeof vis);
memsest(res,0,sizeof res);
for(int i=1;i<=N;++i){ if(!vis[i]){
++vis[i];
for(int j=i+i;j<=N;j+=i){
int t=j;
while(t){
t/=i;
++vis[j];
}
}
}
res[i]=res[i-1]+vis[i];
}
}

gcd & lcm

$lcm(1..n)$

LightOJ 1289

由lcm的性质,我们可知
$$lcm(1..n) = 2^{e_1} * 3^{e_2} * 5^{e_3} … \;\; e_i 为最大的满足 p_i^{e_i} \le n 的值$$
于是我们从小到大枚举k,然后二分求出前i个素数满足$p_i^e \le n$,可以提前处理出前i个数的前缀积,然后答案乘上这个前缀积。
由于这里n很大($10^8$),普通的筛法空间不够,用位图标记,一个 unsigned int 表示32位。
这里肯定用线性筛呀,不用是作死啊。。。
还有一个技巧就是($\mod 2^{32}$) 可以直接用 unsigned int 存然后自然溢出

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<cstdio>
#include<cstring>
#include<vector>
using namespace std;

typedef unsigned int UI;
typedef long long LL;

const int maxn = 1e8 + 2;

UI vis[(maxn+31)/32 + 5];
UI sum[5770000];
int pri[5770000];
int n,tot;

void init()
{
tot = 0;
memset(vis,0,sizeof vis);
for(int i=2;i<maxn;++i)
{
if(!(vis[i/32]&(1<<(i%32)))) pri[tot++] = i;
for(int j=0;j<tot;++j)
{
LL t = (LL)i*pri[j];
if(t > maxn) break;
vis[t/32] |= (1<<(t%32));
if(i % pri[j] == 0) break;
}
}
sum[0] = pri[0];
for(int i=1;i<tot;++i)
{
sum[i] = sum[i-1]*pri[i];
}
}

inline bool ok(int m,int t)
{
LL cur = 1;
for(int i=1;i<=t;++i)
{
cur *= pri[m];
if(cur > n) return false;
}
return true;
}

inline int judge(int t)
{
int l = 0, r = tot-1,m,res = -1 ;
while(l <= r)
{
m = (l+r)>>1;
if(ok(m,t))
{
res = m;
l = m+1;
}
else
{
r = m-1;
}
}
return res;
}


UI solve()
{
UI ans=1;
for(int i=1;;++i)
{
int now = judge(i);
if(now == -1) break;
ans *= sum[now];
}
return ans;
}

int main()
{
int T;
init();
//freopen("test.txt","r",stdin);
scanf("%d",&T);
for(int z=1;z<=T;++z)
{
scanf("%d",&n);
printf("Case %d: %u\n",z,solve());
}
return 0;
}

hdu5407

$$LCM(C_k^0,C_k^1,…,C_k^k) = \frac{LCM(1,2,…,k,k+1)}{k+1}$$