解法
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/submissions/2914912
区間の問題のテクとして、[L,R]の答えをf(R)-f(L-1)で求めるテクがある。
これを使おう。
f(x) := x未満の数で好きな曲が何曲あるか
とすると、答えはf(R)-f(L)で求められる。
[140,170)であれば好きな曲である。
2で割るとを逆に考えて2倍にした区間も好きな曲になることになる。
つまり、[280,340), [560,680), [1120, 1360), [2240, 2720), …が好きな曲になる。
この区間でx未満の個数を数えていけばいい。
順番に2倍していくので、10^10になるまでは60回くらいが上限なので、間に合う。
ll C, D; //--------------------------------------------------------------------------------------------------- ll f(ll x) { vector<ll> v; ll ans = 0; ll L = 140, R = 170; while (L < x) { ans += min(x, R) - L; L *= 2; R *= 2; } return ans; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> C >> D; ll ans = f(D) - f(C); cout << ans << endl; }
