關於LCM(1,2,...n,n+1)與LCM(C(n,0),C(n,1)...C(n,n))的關係？

12-19

這是2015 Multi-University Training Contest 10 其中的1002
題目大家就不需要看了，題解直接給出了公式，但是我實在是想知道為什麼，這些公式是怎麼來的！！！
只有一個問題：
為什麼

$mathrm{lcm}(inom{n}{0},inom{n}{1},cdots,inom{n}{n})=frac{mathrm{lcm}(1,2,cdots,n,n+1)}{n+1}$
如果你覺得證明太麻煩了，請直接給我它屬於什麼定理。。。。你看我都證明一晚上了都沒證明出來。

那麼我自己回答咯

先看看Kummer定理
設m，n為正整數，p為素數，則 $C_{n+m}^{m}$ 含p的冪次等於m+n在p進位下的進位次數。

然後來看看由Kummer定理推出來的推論：

簡單證明下，令 $k=sum_{i=0}^{N}{c_{i}p^{i}}$ ,分兩種情況

對於第一種情況： $k=p^{N+1}-1$

k在p進位的表示下，我們有 $c_{i}$ =p-1,對於任意的 $lin (1,2,..n)$ ,k-l在p進位下都不需要借位，所以根據Kummer定理得到

2.1對於第二種情況 $k e p^{N+1}-1$ ,
我們證明

$v_{p}(C_{k}^{l} )leq N-i_{0}$ 和 $v_{p}(C_{k}^{p^{N}-1} )=N-i_{0}$

我們定義
$i_{0}:=min(i|c_{i} e p-1)$
根據 $i_{0}$ 的定義 $c_{0}=c_{1}=c_{i_{0}-1}=p-1$ ，在p進位下 $k-l$ 的前 $i_{0}$ 位是不需要借位的，所以在p進位下 $k-l$ 發生借位的次數最多等於 $N-i_{0}$ .
根據Kummer定理，我們可以寫成
$v_{p}(C_{k}^{l} )leq N-i_{0}$
2.2現在假設特別情況 $l=p^N-1=sum_{i=0}^{N-1}{(p-1)p^i}$
因為 $c_{0}=c_{1}=c_{i_{0}-1}=p-1$ ，並且 $c_{i_0}$ &

需要從位置 $i_0$ 一直借位到N-1,根據Kummer定理
$v_{p}(C_{k}^{p^{N}-1} )=N-i_{0}$
所以，我們完成了推論的證明！

=====================小小的天，有達達的夢想=======================

現在我們才開始證明
$LCM(C_{K}^{0}, C_{K}^{1},..., C_{K}^{K})=frac{LCM(1,2,...,K,K+1)}{(K+1)}$

我們需要證明:

$v_p(LCM(C_{K}^{0}, C_{K}^{1},..., C_{K}^{K}))=v_p(frac{LCM(1,2,...,K,K+1)}{(K+1)})$

1.先來看看左邊的 $v_p(LCM(C_{K}^{0}, C_{K}^{1},..., C_{K}^{K}))$
同樣令 $k=sum_{i=0}^{N}{c_{i}p^{i}}$ ，對於任意素數p，根據剛才的推論，我們有

2.再來看看右邊的 $v_p(frac{LCM(1,2,...,K,K+1)}{(K+1)})$
令 $t=v_p({LCM(1,2,...,K,K+1)})$ ,於是 $p^tleq k+1<^{t+1}$ 。
根據k在p進位的表達式 $k=sum_{i=0}^{N}{c_{i}p^{i}}$ ， $p^Nleq k$ ，即 $v_p({LCM(1,2,...,K,K+1)})geq N$

如果 $k+1=p^{N+1}$ ,那麼 $v_p({LCM(1,2,...,K,K+1)})= N+1$
如果 $k+1 e p^{N+1}$ ，那麼 $v_p({LCM(1,2,...,K,K+1)})< N+1$ ，所以 $v_p({LCM(1,2,...,K,K+1)})=N$

於是我們有

然後，我們容易得到

由(4)-(3)得到

此時回頭看看

所以我們證明了
$v_p(LCM(C_{K}^{0}, C_{K}^{1},..., C_{K}^{K}))=v_p(frac{LCM(1,2,...,K,K+1)}{(K+1)})$

於是

$LCM(C_{K}^{0}, C_{K}^{1},..., C_{K}^{K})=frac{LCM(1,2,...,K,K+1)}{(K+1)}$
證畢哈哈。感謝 @趙軒昂提供的論文！！

http://arxiv.org/pdf/0906.2295v2.pdf

安利一個整數數列類問題的神器，就是樓上有人提到的OEIS：
The On-Line Encyclopedia of Integer Sequences? (OEIS?)
把數列的前幾項輸進去，當然光是樣例的5個匹配到的數列太多了，我們多算幾個出來然後輸進去好了
1,2,3,12,10,60,105,280,252,2520
匹配的結果只有一個
A002944 - OEIS
這個數列是LCM{1,2,...,n} / n
同時下面的FORMULA裡面提到了Equals LCM of C(n-1, 0), C(n-1, 1), ..., C(n-1, n-1)
LINKS裡面有相關的鏈接，包括 @趙軒昂回答里的那篇paper，證明了這個等式
http://arxiv.org/abs/0906.2295

需要注意的是，不建議過度使用該網站，至少不要養成對OEIS的依賴，尤其是訓練中。。。（雖然我覺得大部分隊伍在做這個題的時候要麼找規律猜的要麼OEIS的吧。。。這個應該沒幾個人能在比賽場上嚴格證明出來吧。。。

水一下。。當時做這道題的時候沒想這麼多直接用遞推一個個算C(n,0)-C(n,n/2)直接求lcm了。。寫完之後測了一下1e6，發現還挺快的(大概0.3秒左右吧)。。誰知道case居然這麼大。。然後就開始找規律了。經提醒找到了lcm(1,...,n)和答案的關係，興奮地寫完提交。。！

結果還是TLE了╮(╯▽╰)╭

OEIS大法好！

我暴力打表發現：對於質數p和整數n滿足若 p^k&<=n&

打了個表看了半天感覺是有規律然而沒找到T_T

我好想問難道過的那近200隊都是這麼做的么....
仰慕朝鮮大兄弟......

number theory
丟鏈接跑，前兩個答案的思路都挺有趣。

這道題是直接丟到oeis上查出來的……上面應該有證明……現場的時候沒來得及看……