首页 > 试题广场 >

最大的奇约数

[编程题]最大的奇约数
  • 热度指数：32005 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数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
算法知识视频讲解
添加回答
Python
🌞☀️🍀🍀🍀🍀🍀头像 🌞☀️🍀🍀🍀🍀🍀
def sum(n):
    n = int(n)
    if n == 1:
        return 1
    if n % 2 == 0:
        return sum(n//2) + n*n//4
    else:
        return sum(n-1) + n
n = input()
print(sum(n))
发表于 2019-08-14 20:27:23 回复(0)
Python
离疏头像 离疏 
N=int(raw_input())
def getSum(n):
    if n==1:
        return 1
    if n%2==0:
        return n*n/4+getSum(n/2) #n为偶数时，奇数的和为n*n/4,偶数的和为getSum(n/2)
    else:
        return n+getSum(n-1) #n为奇数是，和为自身n加上比他小一的偶数的函数和getSum(n-1)
print(int(getSum(N)))

发表于 2018-04-27 11:57:23 回复(1)
Python
labulaka520头像 labulaka520 
num = int(input())
c = 0
while num > 0:
    c += ((num+1)//2)*((num+1)//2)
    num = num //2
print(c)
发表于 2017-09-02 14:55:45 回复(0)
Python
17浪头像 17浪 
#!/usr/bin/env python

def f(x):
    if x % 2 != 0:
       return x
    else:
        return f(x/2)

if __name__ == '__main__':
     NUM = int(raw_input("Please input the number:>"))
     SUM = 0
      for i in range(1, NUM + 1):
            SUM = SUM + f(i)

     print SUM
                
发表于 2016-11-01 14:23:13 回复(1)
Python
蒲公英_23头像 蒲公英_23 
N=input()

sum=0
while(N>0):
    sum+=((N+1)/2)*((N+1)/2)
    N=N/2
print sum

发表于 2016-09-21 19:41:57 回复(0)
提交观点

问题信息

模拟 穷举 数学
来自：网易2017秋招编程题集合
难度：
5条回答 21740浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大的奇约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号