內存限制： 128 MiB時間限制： 100 ms標準輸入輸出題目類型： 傳統評測方式： 文本比較

題目描述

定義函數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

超時代碼：

#include <bits/stdc++.h>
using namespace std;
long long n,ans;
int main(){cin>>n;for(int i=1;i<=n;i+=2){ans+=i;long long x=i;while(x*2<=n){x*=2;ans+=i;}}cout<<ans;
}

_____________________________________________________________________________

太難想了，感覺想出超時代碼已經很不錯了；

寫作不易，點個贊唄!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!?

_____________________________________________________________________________

遞歸折半優化后：?

#include <bits/stdc++.h>
using namespace std;
long long n,ans;
long long f(long long a){long long b=a-1;if(a==1)return 1;if(a%2==1){a--;b++;}return ans=f(a/2)+(1+b)*(b+1)/4;
}
int main(){cin>>n;f(n);cout<<ans;
}

?