解答最大的因子分解

题目

题目描述

设函数f(x)用于表征正整数x的最大奇约数，其中x为自然数中的正整数值。例如，当x=20时，其所有约数按升序排列为1, 2, 4, 5, 10, 20，其中最大的奇约数为5，因此f(20)=5。

对于给定的正整数N，计算f(1)+f(2)+…+f(N)的总和。

输入格式

第1行：一个范围在1到10的9次方之间的正整数N

样例

样例输入解析

    7
    
    
      
    

样例输出

    21
    
    
      
    

数据范围与提示

样例说明

f(1)与f(2)、f(3)、f(4)、f(5)、f(6)及f(7)的数值相加结果为1+1+3+1+5+3+7，总计得出21。

上述内容即为题目

题解

对于奇数而言，其最大的约数即为其自身；而偶数的最大奇约数则是在去除所有偶数因子后所剩余的奇数。因此，一种直观的处理方式是依次遍历并累加这些数值。然而，这种思路的计算复杂度预计为O(n)，尽管我尚无法准确推导出其具体复杂度表达式，但考虑到n的取值范围高达10^9，显然这种方法会导致超时问题。正因如此，有研究者尝试引入记忆化技术以优化性能，但试想一下，若要实