白準2で何回か分けますね(1407)

2分何回ですか。

1.ヒント

1）g（x）=∑k=1xf（k）g（x）=\displaystyle\sum k=1}^{x}f（k）=k=1∑xf（k）=∑k=ABf（k）→g（B）\ g（A \ 1）\displaystyle\ k k=^B}f（k）\\ B（G））-g（B（G（G）））。

2)f(x)f(x)f(x)をリストすると,g(x)g(x)g(x)を求めるルールが見つかる.

2.近接

1) g(x)g(x)g(x)

f(x)f(x)f(x)f(x)を迅速に解くために,f(x)f(x)の規則を探すことを試みたが,いくつか複雑であった.g(x)=∑k=1xf(k)g(x)=\displaystyle\sum k=1}^{x}fg(x)g(x)g(x)g(x)における規則の検索と迅速な解を実現する.
f(x)f(x)f(x)f(x)をリストします.
f(x)=1, 2, 1, 4, 1, 2, 1, 8f(x) = 1,\2,\1,\4,\1,\2,\1,\8f(x)=1, 2, 1, 4, 1, 2, 1, 8
g(x)g(x)g(x)g(x)g(x)は、f(x)f(x)f(x)の累積和として理解することができ、g(x)g(x)g(x)g(x)は、xxx以下の222乗のすべての和である.
ただし111を222で割ると222で割るので重複をなくす必要がある.
∑i=0(2i−2i−1)×(x/2i)\displaystyle\sum_{i=0} (2^i - 2^{i - 1})\times (x/2^i)i=0∑​(2i−2i−1)×(x/2i).
i=0 i=0 i=0(2 i)の場合×(x/2i)(2^i)\times (x/2^i)(2i)×(x/2 i)で例外処理を行います.

3.実施

public class Main {
	static long[] cache = new long[64];
	
	// 2^x
	static long pow(int x) {
		if (x == -1) return 0;
		if (x == 0) return 1;
		if (cache[x] != 0) return cache[x];
		if (x % 2 == 1) return cache[x] = 2 * pow(x - 1);
		return cache[x] = pow(x / 2) * pow(x / 2);
	}
	
	static long g(long x) {
		long ret = 0;
		for (int i = 0; pow(i) <= x; i++)
			ret += (pow(i) - pow(i - 1)) * (x / pow(i));
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Long A = Long.parseLong(st.nextToken());
		Long B = Long.parseLong(st.nextToken());
		System.out.println(g(B) - g(A - 1));
	}

}