SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)-A：Feel the Beat(300)

問題

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_a

制約

  • 140 \le C \lt D \le 10^{15}

考え方

[140 * 2^k, 170 * 2^k) の区間と [c, d) の区間が交差するときの整数解の個数を求める問題。

2 つの区間が交差する区間は下図からもわかるように [max(l, c) , min(r, d)) で求めることができる。

f:id:d_tutuz:20181104204311p:plain

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long c = in.nextLong(), d = in.nextLong();
            long l = 140, r = 170;

            long ans = 0;
            while (true) {

                if (d < l) break;

                long min = Math.max(l, c);
                long max = Math.min(r, d);

                ans += Math.max(max - min, 0);

                l *= 2;
                r *= 2;
            }

            out.println(ans);
        }

ポイント

類題