首页 > 代码库 > acdream 20140730 D题

acdream 20140730 D题

今天见识到了“数学上来先打表”............

#include<iostream>using namespace std;#include<iomanip>#define LL long long/*int lowbit(int n){    int t,cnt = 1;    t = n % 2;    if(t == 1) return 1;    while(t == 0)    {        cnt *= 2;        n /= 2;        t = n % 2;    }    return cnt;}LL d(int n){    LL ans = 0;    for(int i = 1; i <= n; i++)        ans += lowbit(i);    return ans;}*///经过打表,得f(x) = 2 * f( x / 2) + n / 2 + ( n & 1 )LL d(int n){    if(n == 1)return 1;    LL ans = 2 * d(n / 2) + n / 2 + (n & 1);    return ans;}int main(){    int n;    while(cin>>n)    {        cout<<d(n)<<endl;    }    return 0;}