qaqhtml
对于任意非负整数
n
,
m
n, m
n , m
lcm
(
C
n
0
,
C
n
1
,
⋯
,
C
n
m
)
=
lcm
(
n
−
m
+
1
,
n
−
m
+
2
,
⋯
,
n
+
1
)
n
+
1
\text{lcm}(C_n^0,C_n^1,\cdots,C_n^m)=\frac{\text{lcm}(n-m+1,n-m+2,\cdots,n+1)}{n+1}
lcm ( C n 0 , C n 1 , ⋯ , C n m ) = n + 1 lcm ( n − m + 1 , n − m + 2 , ⋯ , n + 1 ) web
v
p
(
n
)
v_p(n)
v p ( n )
p
p
p
n
n
n app
设
m
,
n
(
0
≤
m
≤
n
)
m, n (0\le m\le n)
m , n ( 0 ≤ m ≤ n )
p
p
p
C
n
m
C_{n}^m
C n m
p
p
p
(
n
−
m
)
(n-m)
( n − m )
m
m
m
p
p
p svg
证：令
n
=
(
n
k
n
k
−
1
⋯
n
0
‾
)
p
n=(\overline{n_kn_{k-1}\cdots n_0})_p
n = ( n k n k − 1 ⋯ n 0 ) p
v
p
(
n
!
)
=
∑
i
=
1
k
⌊
n
p
i
⌋
=
∑
i
=
1
k
n
k
n
k
−
1
⋯
n
i
‾
=
∑
i
=
1
k
∑
j
=
i
k
n
j
p
j
−
i
=
∑
j
=
1
k
n
j
∑
i
=
0
j
−
1
p
i
=
∑
i
=
1
k
n
i
p
i
−
1
p
−
1
=
1
p
−
1
(
∑
i
=
1
k
n
i
p
i
−
∑
i
=
1
k
n
i
)
=
1
p
−
1
(
n
−
∑
i
=
0
k
n
i
)
v_p(n!)=\sum_{i=1}^k \left \lfloor \frac{n}{p^i} \right \rfloor=\sum_{i=1}^k \overline{n_kn_{k-1}\cdots n_i}=\sum_{i=1}^k \sum_{j=i}^k n_jp^{j-i}=\sum_{j=1}^k n_j \sum_{i=0}^{j-1} p^i=\sum_{i=1}^k n_i \frac{p^i-1}{p-1} \\ =\frac{1}{p-1}\left(\sum_{i=1}^k n_ip^i-\sum_{i=1}^k n_i \right)=\frac{1}{p-1}\left(n-\sum_{i=0}^k n_i \right)
v p ( n ! ) = i = 1 ∑ k ⌊ p i n ⌋ = i = 1 ∑ k n k n k − 1 ⋯ n i = i = 1 ∑ k j = i ∑ k n j p j − i = j = 1 ∑ k n j i = 0 ∑ j − 1 p i = i = 1 ∑ k n i p − 1 p i − 1 = p − 1 1 ( i = 1 ∑ k n i p i − i = 1 ∑ k n i ) = p − 1 1 ( n − i = 0 ∑ k n i )
m
=
(
a
k
a
k
−
1
⋯
a
0
‾
)
p
,
n
−
m
=
(
b
k
b
k
−
1
⋯
b
0
‾
)
p
m=(\overline{a_ka_{k-1}\cdots a_0})_p, n-m=(\overline{b_kb_{k-1}\cdots b_0})_p
m = ( a k a k − 1 ⋯ a 0 ) p , n − m = ( b k b k − 1 ⋯ b 0 ) p
v
p
(
C
n
m
)
=
v
p
(
n
!
)
−
v
p
(
m
!
)
−
v
p
(
(
n
−
m
)
!
)
=
1
p
−
1
∑
i
=
0
k
(
a
i
+
b
i
−
n
i
)
v_p(C_n^m)=v_p(n!)-v_p(m!)-v_p((n-m)!)=\frac{1}{p-1}\sum_{i=0}^k (a_i+b_i-n_i)
v p ( C n m ) = v p ( n ! ) − v p ( m ! ) − v p ( ( n − m ) ! ) = p − 1 1 i = 0 ∑ k ( a i + b i − n i ) spa
故此式即
(
n
−
m
)
+
m
(n-m)+m
( n − m ) + m
p
p
p 翻译
设
n
=
(
n
k
n
k
−
1
⋯
n
0
‾
)
p
,
m
=
(
m
k
m
k
−
1
⋯
m
0
‾
)
p
n=(\overline{n_kn_{k-1}\cdots n_0})_p, m=(\overline{m_km_{k-1}\cdots m_0})_p
n = ( n k n k − 1 ⋯ n 0 ) p , m = ( m k m k − 1 ⋯ m 0 ) p
k
k
k
n
n
n
m
m
m
max
0
≤
l
≤
m
v
p
(
C
n
l
)
=
{
0
n
=
p
k
+
1
−
1
0
m
≤
p
i
0
−
1
max
{
i
−
i
0
+
1
∣
i
0
≤
i
<
k
,
m
≥
n
i
n
i
−
1
⋯
n
i
0
+
1
(
n
i
0
+
1
)
‾
p
i
0
}
otherwise
\max_{0\le l\le m} v_p(C_n^l)= \begin{cases} 0 & n=p^{k+1}-1 \\ 0 & m\le p^{i_0}-1 \\ \max\{i-i_0+1 | i_0\le i< k, m\ge \overline{n_i n_{i-1} \cdots n_{i_0+1}(n_{i_0}+1)}p^{i_0}\} & \text{otherwise} \end{cases}
0 ≤ l ≤ m max v p ( C n l ) = ⎩ ⎪ ⎨ ⎪ ⎧ 0 0 max { i − i 0 + 1 ∣ i 0 ≤ i < k , m ≥ n i n i − 1 ⋯ n i 0 + 1 ( n i 0 + 1 ) p i 0 } n = p k + 1 − 1 m ≤ p i 0 − 1 otherwise orm
这里当
n
≠
p
k
+
1
−
1
n\not= p^{k+1}-1
n = p k + 1 − 1
i
0
=
min
{
i
∣
n
i
≠
p
−
1
}
i_0=\min\{i \mid n_i\not= p-1\}
i 0 = min { i ∣ n i = p − 1 } xml
人话：先特判掉两种状况；咱们枚举每种进位次数，找到最小的
l
l
l
(
n
−
l
)
+
l
(n-l)+l
( n − l ) + l
i
0
i_0
i 0
p
−
1
p-1
p − 1
i
0
i_0
i 0
m
i
m
i
−
1
⋯
m
i
0
+
1
(
m
i
0
+
1
)
‾
p
i
0
\overline{m_i m_{i-1} \cdots m_{i_0+1}(m_{i_0}+1)}p^{i_0}
m i m i − 1 ⋯ m i 0 + 1 ( m i 0 + 1 ) p i 0 htm
更近一步，若是咱们舍去
m
m
m
m
=
(
m
t
m
t
−
1
⋯
m
0
‾
)
p
m=(\overline{m_tm_{t-1} \cdots m_0})_p
m = ( m t m t − 1 ⋯ m 0 ) p
max
0
≤
l
≤
m
v
p
(
C
n
l
)
=
{
0
n
=
p
k
+
1
−
1
0
t
<
i
0
t
−
i
0
m
<
(
n
t
n
t
−
1
⋯
n
0
‾
)
+
1
max
{
q
∣
q
≥
t
,
∀
t
<
j
≤
q
,
n
t
=
0
}
−
i
0
+
1
otherwise
\max_{0\le l\le m} v_p(C_n^l)= \begin{cases} 0 & n=p^{k+1}-1 \\ 0 & t<i_0 \\ t-i_0 & m<(\overline{n_tn_{t-1}\cdots n_0})+1 \\ \max\{q | q\ge t, \forall t<j\le q, n_t=0\}-i_0+1 & \text{otherwise} \end{cases}
0 ≤ l ≤ m max v p ( C n l ) = ⎩ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎧ 0 0 t − i 0 max { q ∣ q ≥ t , ∀ t < j ≤ q , n t = 0 } − i 0 + 1 n = p k + 1 − 1 t < i 0 m < ( n t n t − 1 ⋯ n 0 ) + 1 otherwise ip
设
n
=
(
n
k
n
k
−
1
⋯
n
0
‾
)
p
,
m
=
(
m
t
m
t
−
1
⋯
m
0
‾
)
p
n=(\overline{n_kn_{k-1}\cdots n_0})_p, m=(\overline{m_tm_{t-1}\cdots m_0})_p
n = ( n k n k − 1 ⋯ n 0 ) p , m = ( m t m t − 1 ⋯ m 0 ) p
k
,
t
k,t
k , t
n
,
m
n,m
n , m
首先特判掉
m
=
0
m=0
m = 0
当
n
=
p
k
+
1
−
1
n=p^{k+1}-1
n = p k + 1 − 1
max
v
p
(
l
)
=
v
p
(
n
+
1
)
\max v_p(l)=v_p(n+1)
max v p ( l ) = v p ( n + 1 )
RHS
=
v
p
(
n
+
1
)
−
v
p
(
n
+
1
)
=
0
\text{RHS}=v_p(n+1)-v_p(n+1)=0
RHS = v p ( n + 1 ) − v p ( n + 1 ) = 0
设
i
0
=
min
{
i
∣
n
i
≠
p
−
1
}
i_0=\min\{i | n_i\not= p-1\}
i 0 = min { i ∣ n i = p − 1 }
v
p
(
n
+
1
)
=
i
0
v_p(n+1)=i_0
v p ( n + 1 ) = i 0
设
i
1
=
min
{
i
∣
(
n
+
1
)
i
≠
(
n
−
m
+
1
)
i
}
i_1=\min\{i | (n+1)_i\not= (n-m+1)_i\}
i 1 = min { i ∣ ( n + 1 ) i = ( n − m + 1 ) i }
max
v
p
(
l
)
=
i
1
\max v_p(l)=i_1
max v p ( l ) = i 1
当
t
<
i
0
t<i_0
t < i 0
max
v
p
(
l
)
=
i
0
\max v_p(l)=i_0
max v p ( l ) = i 0
RHS
=
0
\text{RHS}=0
RHS = 0
当
m
<
(
n
t
n
t
−
1
⋯
n
0
‾
)
+
1
m<(\overline{n_tn_{t-1}\cdots n_0})+1
m < ( n t n t − 1 ⋯ n 0 ) + 1
(
n
+
1
)
−
m
(n+1)-m
( n + 1 ) − m
t
+
1
t+1
t + 1
max
v
p
(
l
)
=
t
\max v_p(l)=t
max v p ( l ) = t
v
p
(
n
+
1
)
=
i
0
v_p(n+1)=i_0
v p ( n + 1 ) = i 0
RHS
=
t
−
i
0
\text{RHS}=t-i_0
RHS = t − i 0
otherwise
\text{otherwise}
otherwise
max
{
q
∣
q
≥
t
,
∀
t
<
j
≤
q
,
n
t
=
0
}
+
1
\max\{q | q\ge t, \forall t<j\le q, n_t=0\}+1
max { q ∣ q ≥ t , ∀ t < j ≤ q , n t = 0 } + 1
v
p
(
n
+
1
)
=
i
0
v_p(n+1)=i_0
v p ( n + 1 ) = i 0
RHS
=
t
−
i
0
\text{RHS}=t-i_0
RHS = t − i 0
咱们证实了
v
p
(
lcm
(
C
n
0
,
C
n
1
,
⋯
,
C
n
m
)
)
=
v
p
(
lcm
(
n
−
m
+
1
,
n
−
m
+
2
,
⋯
,
n
+
1
)
n
+
1
)
v_p(\text{lcm} (C_n^0, C_n^1, \cdots, C_n^m))=v_p(\frac{\text{lcm}(n-m+1,n-m+2,\cdots,n+1)}{n+1})
v p ( lcm ( C n 0 , C n 1 , ⋯ , C n m ) ) = v p ( n + 1 lcm ( n − m + 1 , n − m + 2 , ⋯ , n + 1 ) )
lcm
(
C
n
0
,
C
n
1
,
⋯
,
C
n
m
)
=
lcm
(
n
−
m
+
1
,
n
−
m
+
2
,
⋯
,
n
+
1
)
n
+
1
\text{lcm}(C_n^0,C_n^1,\cdots,C_n^m)=\frac{\text{lcm}(n-m+1,n-m+2,\cdots,n+1)}{n+1}
lcm ( C n 0 , C n 1 , ⋯ , C n m ) = n + 1 lcm ( n − m + 1 , n − m + 2 , ⋯ , n + 1 )