最大公约数 Plus -----HWOJ23

题目：求C2n1,C2n3,C2n5,⋅⋅⋅C2n2n−1,的最大公约数。\mathrm{C}_{2n}^1,\mathrm{C}_{2n}^3,\mathrm{C}_{2n}^5,···\mathrm{C}_{2n}^{2n - 1},的最大公约数。

解答代码：

1
2
3
4
5
6
/int main() {
    int n;
    scanf("%d", &n);
    printf("%d", (n << 1) & (-(n << 1)));
    return 0;
}

数学解法分析：

由题目可以想到二项式定理。

∵①(1+1)2n=C2n0+C2n1+C2n2+...+C2n2n=22n(1+1)^{2n} = \mathrm{C}_{2n}^0 + \mathrm{C}_{2n}^1 + \mathrm{C}_{2n}^2 +...+\mathrm{C}_{2n}^{2n} = 2^{2n}

②(1−1)2n=C2n0−C2n1+C2n2+...+C2n2n=0(1-1)^{2n} = \mathrm{C}_{2n}^0 - \mathrm{C}_{2n}^1 + \mathrm{C}_{2n}^2 +...+\mathrm{C}_{2n}^{2n} = 0

:arrow_right: C2n1+C2n3+...+C2n2n−1=22n2=22n−1\mathrm{C}_{2n}^1 + \mathrm{C}_{2n}^3 +...+\mathrm{C}_{2n}^{2n - 1} = \frac{2^{2n}}{2} = 2^{2n - 1}

又∵奇数次系数之和22n−12^{2n - 1} 不能被奇数整除，所以最大公因数不含奇数因子。

证明：

∵kn1+kn2+k...=k(n1+n2+...)kn_1 + kn_2 + k_{...}= k(n1 + n2 + ...), 其中k为最大公约数，如果存在其他质数因子，则该数列之和一定能被这个质数因子整除。

反证，如果公约数有非2的质因子，则一定有序列之和可以被质数整除，然而22n−12^{2n-1}

只有2作为因子，故此不成立。

:arrow_right:可以得出，最大公约数中，没有2以外的质因子，既最大公约数一定是2的幂数。

由排列组合Cn0到Cnn为单驼峰状，在Cnn2或Cnn2+1处达到峰值\mathrm{C}_n^0 到\mathrm{C}_n^n为单驼峰状，在\mathrm{C}_n^{\frac{n}{2}}或\mathrm{C}_n^{\frac{n}{2}+ 1}处达到峰值，在数列{C2n1...C2n2n−1\mathrm{C}_{2n}^1...\mathrm{C}_{2n}^{2n - 1}}中，从C2n1\mathrm{C}_{2n}^1后的每一项中2的个数都比C2n1\mathrm{C}_{2n}^1多或相等

∴可以使用缩放的思想，将最大的数放大为数列相加之和，最小数锁定为C2n1\mathrm{C}_{2n}^1,只用求这两个数的最大公约数.

:arrow_right: 题意为求2n和22n−12^{2n-1}的最大公约数，既求2n中有多少个2

1
2
3
int gcd(int a, int b) {
    return b ? b ： gcd(b, a % b);
}

从二进制思考则可以进一步简化：

二进制下每左移一位便多一个2作为因子，所以最后可以转化为2n末尾有多少个0，也就是最低位的1是几。

1
2
3
int lowbit(int t) {
    return t & (-t);
}

解释：

计算机中负数以补码进行存储，则(12)10=(00001100)2(12)_{10} = (00001100)_2, (−11)10=(00000100)2(-11)_{10}=(00000100)_2

即可得出二进制中最低位的1，是多大，也就是最大公约数。