本文主要是介绍【题解】最大奇约数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
题目描述
定义函数f(x)表示x的最大奇约数,这里x表示正整数。例如,f(20) = 5,因为20的约数从小到大分别有:1, 2, 4, 5, 10, 20,其中最大的奇约数为5。
给出正整数N,求f(1)+f(2)+…+f(N)
输入格式
第1行:1个正整数N 1<=N<=10^9
样例
样例输入
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,想都不用想
会TLE
于是有人想到了用记忆化,但你想想你写一个:
int Memory[1000000005];
<
这篇关于【题解】最大奇约数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!