小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数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 total
print(gettotal(n))
最后,解法为:
n = int(input())
def gettotal(n):
total = 0
while n:
total += ((n+1)//2)**2
n //=2
return total
print(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