之前碰到一道算法题,本质上是一道数论题,这里简单记录下。

另外查阅之前写的资料,发现也记录过几个有意思的数学小问题,以后统一归类为[有趣的算法和数学],后续碰到有意思的问题都会加以总结,以数学和算法为主。

参考资料:

https://www.cnblogs.com/tkandi/p/10417644.html
https://tieba.baidu.com/p/4014319070?red_tag=3594283516

问题描述

设$n$是正整数,求 $\binom {2 n}{1}, \binom{2 n}{3}, \cdots, \binom{2 n}{2 n-1}$ 的最大公约数$d$。

思路

这个问题最重要的一点是想到如果

那么

为什么要利用这点呢,这是因为此处有如下事实:(由二项式定理)

所以

从而$d$必然为如下形式

接下来就是计算$\binom{2n}{2i-1}$中$2$的次数,这部分可以利用Kummer定理(参考https://www.cnblogs.com/tkandi/p/10417644.html):

其中$v_{p}(n)$为$n$标准分解后$p$的次数($p$为质数),$s_p(n)$为$n$在$p$进制下的数位和。

此处取$p=2,n=2n,m=2i-1$,所以

假设

那么$2n$的二进制表达式必然为

(这里假设$1,2,\ldots,2n$都用$k+j+1$位二进制数表示)

那么

注意$2i-1,2n-2i+1$为奇数,并且都小于$2n$,所以形式必然如下:

假设

那么

注意到

所以必然有

(这里$c_i$的含义是进位。)

那么

从而

所以

这推出($d$是最大公约数)

注意到

所以可得

另一方面

这说明

综上

其中

接下来说明如何用计算机快速求解$k$,根据定义可得

那么

因此

因此C语言中快速计算的方法为

(-2n) & (2n)