时间戳

首页 > 解决方案 > 求所有整数 1 到 N 的最大奇数之和

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

问题描述

给我一个正整数 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;

标签： c++algorithmmath

解决方案

[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)

ETC...

即，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

推荐阅读