c++ - 求所有整数 1 到 N 的最大奇数之和

Question

我有一个正整数 N。f(N) 是 N 的最大奇数。

求和 (f(1)+f(2)+f(3)+....f(N))%m。

如果 N 的阶数为 10^18 而 m 最大为 10^9，那么应该采用哪种更快的算法？

暴力算法示例:

int sum=0;
int a[n+1];
for(int i=1;i<=n;i++){
    if(i%2!=0)
        a[i] = i;
    else
        a[i] = a[i/2];
}
for(int i=1;i<=n;i++){
    sum+=a[i];
}
cout<<sum;

Answer 1

[1,N]范围内的奇数之和为奇数个数的平方，即((N+1)/2)^2，其中'/'表示整数除法。我们称之为 p(N)。

我们仍然需要找到 [1,N] 范围内偶数的最大奇数之和。我们可以将范围内的偶数除以除以它们的 2 的最大幂。

For 1 power of 2: p(N/2)
For 2 powers of 2: p(N/4)
For 3 powers of 2: p(N/8)

等...

即，f(N) = p(N) + p(N/2) + p(N/4) + p(N/8) + ...

这是 N = 1, 2, ..., 20 的结果:

N,  f(N)
1,    1
2,    2
3,    5
4,    6
5,   11
6,   14
7,   21
8,   22
9,   31
10,  36
11,  47
12,  50
13,  63
14,  70
15,  85
16,  86
17, 103
18, 112
19, 131
20, 136