求所有整数 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