首页 > 代码库 > 函数求值(swust oj0274)

函数求值(swust oj0274)

函数求值(0274)

Time limit(ms): 1000
Memory limit(kb): 65535
Submission: 1767
Accepted: 324
Accepted

14级卓越班选拔D 15级卓越班选拔D 16级卓越班选拔D

定义函数g(n)为n最大的奇数因子。 求f(n)=g(1)+g(2)+g(3)+…+g(n)。

Description

有多组测试数据(不超过50)。 每组数据一个整数n(0 < n <= 10^8)。

Input

输出对应的f(n),每组数据占一行。

Output

1
2
3
4
5
1
2
4
7
 
Sample Input

1
2
3
4
5
1
2
6
21
 
Sample Output

 
 
//等差数列公式推导 当m为奇数时  A1 = 1; d=2; An=m; 则S=(An+1)(An+1)/4;
//这道题的思路就是 将 1—n 的奇数全部加起来后   剩下的偶数集体除以2 形成一个新的 数列 
比如F( 1 2 3 4 5 6 7 8 9 10)
等于S(1+3+5+7+9) + F(2 ,4 ,6 ,8 ,10)
等于(9+1)*(9+1)/4   +  F(1,2,3,4,5)
.......
...
 
#include<iostream>
#define LL long long
using namespace std;
LL n,a;
LL fun(const LL x)
{
    if(x==0) return 0;
    if(x%2==1) return (x+1)*(x+1)/4+fun(x/2);
    else return x*x/4+fun(x/2);
}
int main()
{
    while(cin>>n)
    {
        cout<<fun(n)<<endl;
    }
    return 0;
 } 

 

函数求值(swust oj0274)