Submission #64571484

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define i64 int64_t

void solve() {
  i64 N;
  cin >> N;

  i64 ans = 0;
  i64 pw2 = 1;
  for (int i = 0; i < 60; i++) {
    pw2 *= 2;
    if (pw2 > N) {
      break;
    }
    // Find # of perfect squares that fit
    i64 lo = 1, hi = 1e9;
    i64 best = lo;
    while (lo <= hi) {
      i64 mid = (lo + hi) / 2;
      if (pw2 > N / (mid * mid)) {  // pw2*mid^2>N, avoids overflow
        hi = mid - 1;
      } else {
        best = mid;
        lo = mid + 1;
      }
    }
    ans += (best + 1) / 2;  // only allow odd b for b^2
  }

  cout << ans << '\n';
}

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  solve();
  return 0;
}

Submission Info

Judge Result