蓝桥杯2025.5.23每日一题-儿童数

勒让德公式

v

p

(

n

!

)

=

∑

k

=

1

∞

⌊

n

p

k

⌋

v_p(n!) = \\sum_{k=1}^{\\infty} \\left\\lfloor \\frac{n}{p^k} \\right\\rfloor

vp​(n!)=k=1∑∞​⌊pkn​⌋

可以用这个公式计算

n

!

n!

n! 的质因数

p

p

p 的次数。

整除的充要条件

设

a

a

a 和

b

b

b 是正整数，且它们的质因数分解为：

a

=

p

1

α

1

p

2

α

2

⋯

p

k

α

k

,

b

=

p

1

β

1

p

2

β

2

⋯

p

k

β

k

a = p_1^{\\alpha_1} p_2^{\\alpha_2} \\cdots p_k^{\\alpha_k}, \\quad b = p_1^{\\beta_1} p_2^{\\beta_2} \\cdots p_k^{\\beta_k}

a=p1α1​​p2α2​​⋯pkαk​​,b=p1β1​​p2β2​​⋯pkβk​​

（若某个质数

p

i

p_i

pi​ 不在

a

a

a 或

b

b

b 的分解中，则对应的指数

α

i

\\alpha_i

αi​ 或

β

i

\\beta_i

βi​ 视为

0

0

0。）

整除的充要条件

a

∣

b

a \\mid b

a∣b 当且仅当

∀

i

∈

{

1

,

2

,

…

,

k

}

,

α

i

≤

β

i

\\forall i \\in \\{1, 2, \\dots, k\\}, \\alpha_i \\leq \\beta_i

∀i∈{1,2,…,k},αi​≤βi​。

即

a

a

a 的所有质因数的幂次都不超过

b

b

b 的对应幂次。