提出 #50156221

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define N 100007
#define all(x) x.begin(),x.end()
ll binmultiply(ll a,ll b,ll m){ll res=0;while(b>0){if(b&1)res=(res+a)%m;a=(a+a)%m;b=b>>1;}return res;}
ll expo(ll a, ll b, ll m) {ll res = 1; while (b > 0) {if (b & 1)res = binmultiply(res,a,m)% m; a = binmultiply(a,a,m) % m; b = b >> 1;} return res;}
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m

map<int,int> dp;

int solve2(int x){
    if(x<2) return 0;
    if(dp.find(x)!=dp.end()){
        return dp[x];
    }
    if(x%2==0){
        dp[x] = x + 2*solve2(x/2);
    }
    else{
        dp[x] = solve2(x/2) + solve2((x+1)/2) + x;
    }
    return dp[x];
}
    
    
void solve()
{
    int n;cin >> n;
    cout << solve2(n) << endl;
}
    
    
int32_t main()
{
    IOS;
    ll t=1;
    //cin >> t;
    while(t--)
        {
            solve();
        }
    return 0;
}

提出情報

ジャッジ結果