最大奇约数（递归 C++）

最大奇约数
总时间限制: 1000ms 内存限制: 65536kB
描述
定义函数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
输出
第1行：1个正整数，表示题目所求答案
样例输入

7

样例输出

21

提示
样例说明
f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+3+7=21

思路点拔：找呗，各种递归关系,举个例子哈，
例如：n=6；则原式等于f(1)+f(2)+…+f(6);
一个奇数的最大奇约数是它本身，那么原式
等于1+f(2)+3+f(4)+5+f(6)
此时我们需要明确一点：2n的最大奇约数就是
n的奇约数，那么，原式就进一步变成了1+f(1)+3+f(2)+5+f(3);
所以，当n为偶数时，sum=((n-1+1)/2)/2+sum(1,2,3)
也就是sum=n*n/4+sum(n/2)
但是当n等于奇数时，又有点变化了
当n为奇数时，我们可以变化一下，将原式变为
f(1)+f(2)+…+f(n)=sum(n-1)+n;(想一想，为什么不是加f(n))

#include<cstdio>
#include<cstring>
long long sum(long long x)   //注意：本题数据大，所以这个函数类型是longlong
{
    if(x==1||x==2) //递归出口
    {
        return 1;
    }
    if(x%2==0) //如果是奇数
    {
        return x*x/4+sum(x/2); //就执行奇数的递归关系
    }
    return sum(x-1)+x; //否则就执行偶数的递归关系
}
int main()
{
    long long n; 
    scanf("%lld",&n);
    printf("%lld",sum(n)+1); //输出结果
    return 0;
}
/*本题极易超时（我超了3次时，后来听老师评讲的时候才恍然大悟），但是这种题往
往在竞赛中容易出现，所以大家要学会估计自己的程序的时间复杂度，否则就会白白丢
分的*/