当前位置:首页 > 递推 > 正文
SSOJ1341最大奇因数求和
366+

题目大意:我们定义f(X)为X最大的奇数因数,比如f(18)=9,先给出n,求f(1)+f(2)+…+f(n)

输入

一个整数,n。

输出

输出连加的和。

样例输入

5

样例输出

11

提示

30%:n<=1000

60%:n<=1000000

100%:n<=1000000000

解题思路

设s(n)=f(1)+f(2)+…+f(n),由于奇数的最大奇因数是自己本身,偶数的最大奇因数跟他除以2的最大奇因数一样,找规律可得:

当n是奇数的时候,s(n) = n + s(n-1);

当n是偶数的时候,f(1)+f(3)+f(5)+…+f(n-1) = 1+3+5+…+n-1 = n*n/4,f(2)+f(4)+…+f(n) = f(1)+f(2)+…+f(n/2),即s(n) = s(n/2) + n*n/4。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

SSOJ1341最大奇因数求和:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter