Project Euler 704 Factors of Two in Binomial Coefficients

Posted on | | 阅读数 次
Words count in article: 550 | Reading time ≈ 3

开启传送门

题目描述

Define $g(n,m)$ to be the largest integer k such that $2^k$ divides $(_m^n)$. For example, $(_5^{12})=792=2^3⋅3^2⋅11$, hence $g(12,5)=3$. Then define $F(n)=max{g(n,m):0\leq m\leq n}$. $F(10)=3$ and $F(100)=6$.

Let $S(N) = \sum_{n=1}^N F(n)$. You are given that $S(100)=389$ and $S(107)=203222840$.

Find $S(10^{16})$.

题意

定义 $g(n,m)$ 表示组合数 $C_n^m$ 唯一分解后，素因子 $2$ 的指数。

定义 $F(n)$ 为 $max{g(n,m):0\leq m\leq n}$

定义 $S(n)$ 为 $\sum_{n=1}^N F(n)$

求 $S(10^{16})$

分析

打个表可以很容易得到 $F(n)$ 对应的 $m$ 的关系为：$n+1-upperbit(n+1) = m$

其中 $upperbit(x)$ 表示 $x$ 二进制下的最高位。

然后就是分块随便搞一搞就行了。

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>

using namespace std;
const long long upper = 1e16;
//const long long upper = 1e7;

long long cal(long long a) { // 1! * 2! * ... * a! 有多少个2{{{
    long long ans = 0;
    long long buf = a;
    long long len = 1;
    while (a >> 1) {
        a >>= 1;
        len <<= 1;
        long long x = buf - (len - 1);
        // 1..1  2..2  3..3
        long long pre = x / len;
        ans += pre * (pre + 1) / 2 * len;
        if (x % len) {
            ans += (pre + 1) * (x % len);
        }
    }
    return ans;
}/*}}}*/
long long cal2(long long a) { // a! 有多少个2{{{
    long long ans = 0;
    while (a) {
        a >>= 1;
        ans += a;
    }
    return ans;
}/*}}}*/
int main() {
    long long n = 0;
    long long ans = cal(upper);
    long long base;
    for (base = 2; n + base <= upper; base <<= 1) {
        n += base;
        ans -= cal(base - 1);
        ans -= cal2(n - base + 1) * base;
    }
    ans -= cal(upper - n - 1);
    ans -= cal2(n + 1) * (upper - n);
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main

import "fmt"

const (
	upper = int64(10000 * 10000 * 10000 * 10000)
)

func cal(a int64) int64 {
	ans := int64(0)
	buf := int64(a)
	len := int64(1)
	for ; a/2 > 0; {
		a >>= 1
		len <<= 1
		x := buf - (len - 1)
		pre := x / len
		ans += pre * (pre + 1) / 2 * len
		ans += (pre + 1) * (x % len)
	}
	return ans
}

func cal2(a int64) int64 {
	ans := int64(0)
	for ; a > 0; {
		a >>= 1
		ans += a
	}
	return ans
}

func main() {
	n := int64(0)
	ans := cal(upper)
	base := int64(2)
	for ; n+base <= upper; base <<= 1 {
		n += base
		ans -= cal(base - 1)
		ans -= cal2(n-base+1) * base
	}
	ans -= cal(upper - n - 1)
	ans -= cal2(n+1) * (upper - n)
	fmt.Printf("%d", ans)
}