Reincarnation

正因为梦易碎，才格外美好。

勒让德定理（Legendre）

发表于 更新于 分类于 ，
本文字数： 4.4k 阅读时长 ≈ 4 分钟

天空即为极限。

该定理在数学领域的运用我并不是很了解，但勒让德定理在 领域中一般可以用于优化 或者对质数分解进行快速运算中。

内容 & 证明

令 ，设 表示 的完全质因数分解后得到的 的指数。

则有：

其中 表示 的整数部分，可以理解为下取整。

证明

考虑求 ，得到：，设 表示 分解出质数 有 个的数的个数。可以得到：

设 ，则得到：

然后比较奇妙的一点是可以证明：。

我们知道，在 中，一共有 个数能够被 整除。而能被 整除就一定能被 整除。

所以，可以得到 。

证毕

应用

阶乘优化

高精度阶乘

求 对 取模后的结果。

数据范围：，保证 是质数。

直接考虑枚举质数，并对 求出其指数。然后相乘即可。抛开快速幂不谈的话，这是一个亚线性的过程。

实际上，求阶乘就是求一个 的过程， 的质数个数期望为 个，而根据调和级数后面那个式子枚举倍数的时间复杂度为 的，所以计算总时间复杂度为 。

例题选讲

最小倍数

题目简介

题目名称：最小倍数
题目来源：

评测链接：https://loj.ac/p/530

形式化题意：给定 ，求最小的 满足 。其中有 ， 表示从小到大的第 个质数。多测。

数据范围：

考虑到勒让德定理对任意质数是独立的，所以我们可以一个质数一个质数来考虑，并得到一个 表示满足 有 个的最小 ，然后对于所有的 取 即可。因为这里的 具有单调性，所以我们可以二分求解。

时间复杂度 ，说是过不了，还是过了。需要注意的是，在计算 时，最好不要枚举 ，因为这样很可能造成 爆 int 甚至 long long 的情况，可以考虑每一次计算 ，用除法代替乘法解决。

AC Code
 
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
94
95
96
// ----- Eternally question-----
// Problem: #530. 「LibreOJ β Round #5」最小倍数
// Contest: LibreOJ
// URL: https://loj.ac/p/530
// Memory Limit: 256 MB
// Time Limit: 900 ms
// Written by: Eternity
// Time: 2023-03-20 08:21:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e4+10,MAXM=1e2+10;
int Test,M;
int Pri[MAXN],Tot;
bool Is[MAXN];
inline void sieve(int n)
{
	Is[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!Is[i]) Pri[++Tot]=i;
		for(int j=1;j<=Tot&&i*Pri[j]<=n;++j)
		{
			Is[i*Pri[j]]=1;
			if(i%Pri[j]==0) break;
		}
	}
}
inline ll check(ll n,ll p)
{
	ll res=0;
	for(ll x=p;x<=n;n/=p) res+=n/x;
	return res;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	sieve(MAXN-10);
	while(Test--)
	{
		read(M);ll N=1;
		for(int i=1;i<=M;++i)
		{
			ll e;read(e);
			ll l=N,r=e*Pri[i],res=r;
			while(l<=r)
			{
				ll mid=(l+r)>>1;
				if(check(mid,Pri[i])<e) l=mid+1;
				else r=mid-1,res=mid;
			}
			checkMax(N,res);
		}
		write(N,'\n');
	}
	return 0;
}
/*

*/

但这道题似乎是有一支 的做法的。

考虑勒让德定理的本质，也就是 ，我们知道，如果将一个 进制的数转化为十进制，有公式：

而我们可以发现，联系上述式子可以得到：

有些类似于我们证明中得到的 。所以我们可以预处理出所有的 ，并将 拆分为 进制数直接算贡献，省去二分的过程。得到 的算法。

代码就不贴了，大家应该都会写。

相关文章