题目

小易是一个数论爱好者，并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题： 定义函数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)
输入例子:
7
输出例子:
21

代码

1.0 之什么都不想

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author: Ming Jia
# @Date:   2017-02-09 22:53:51
# @Last Modified by:   Ming Jia
# @Last Modified time: 2017-09-24 01:21:28
from __future__ import print_function


def msn(n, list_name):
    """
    Calculate the maximum singular number(最大奇约数) of n.

    :param n: The number you want to deal with.
    :param list_name: A list contain all of the msn from 1 to n-1.
    :return The msn of n.
    """
    if n % 2 == 1:
        return n
    else:
        return list_name[n / 2 - 1]


if __name__ == '__main__':
    n = 7
    number_list = []
    for i in range(n):
        number_list.append(msn(i + 1, number_list))
    print(sum(number_list))

当n = 7时输出21，没毛病。
but ~ 敲 ~ 黑 ~ 版

输入一个整数N (1 ≤ N ≤ 1000000000)

速度没问题~内存却~
输入最大的值，果断内存爆掉~

2.0 考虑内存占用

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author: Ming Jia
# @Date:   2017-02-09 22:53:51
# @Last Modified by:   Ming
# @Last Modified time: 2017-09-25 09:29:56
from __future__ import print_function


def msn(n):
    """
    Calculate the maximum singular number(最大奇约数) of n.

    :param n: The number you want to deal with.
    :return The msn of n.
    """
    tail = 0
    number = n / 2
    if n % 2 == 1:
        tail = n
    else:
        tail = 0
    i = 1
    result = 0
    while i <= number:
        result += i**2
        i += 1

    result += tail
    return result


if __name__ == '__main__':
    n = 1000000000
    print(msn(n))

将从1到n的数分为奇数和偶数，奇数的msn是本身，偶数的除以2后，继续分为奇数和偶数~~
1 = 1²
1 + 3 = 2²
……
1 + 3 + 5 + 7 + 9 = 5²
所以_嗯结果就是这样~