本文共 1041 字，大约阅读时间需要 3 分钟。
小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数f(x)为x最大的奇数约数，x为正整数。 例如:f(44) = 11.
现在给出一个N，需要求出 f(1) + f(2) + f(3).......f(N) 例如： N = 7 f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21 小易计算这个问题遇到了困难，需要你来设计一个算法帮助他。输入一个整数N (1 ≤ N ≤ 1000000000)
输出一个整数，即为f(1) + f(2) + f(3).......f(N)
示例1
7
21
题目思路：
最开始时，想到了之前做过的，想按照这个思路求解，结果解出来复杂度太高。
然后，看到了评论中的，奇数最大即为自己，偶数一直除2到变成奇数为止，然后思路变成了将所有数字放在数组中，for循环遍历每个数，奇数不变，偶数则一直除2到变成奇数为止，结果空间复杂度太高。
然后，参考评论中的解法，for循环，第一次求到n的所有奇数的和，然后n=n//2，然后继续求和，代码如下，但是仍然超出了空间限制
n = int(input())def gettotal(n): total = 0 while n: a=[i for i in range(1,n+1,2)] total=total+sum(a) n=n//2 return totalprint(gettotal(n))
最后，解法为：
n = int(input())def gettotal(n): total = 0 while n: total += ((n+1)//2)**2 n //=2 return totalprint(gettotal(n))
理解为：当n是奇数时，求每轮奇数和时，为1+3+...+n=[(n+1)/2]*[(n+1)/2]，第一个(n+1)/2可以理解为求出了首尾相加然后除以2，第二个(n+1)/2可以理解为其中奇数个数，当n是偶数时，其中元素个数为n/2==(n+1)//2，而首尾相加除以2仍然是(n+1)/2，所以，最终每一轮所加上的为((n+1)//2)**2
转载地址：http://oeyai.baihongyu.com/