Codeforces Round #132 (Div. 2) E : Periodical Numbers

問題概要

整数xを2進表記して、その文字列表現が長さ2以上の周期を持っているときxを周期的と定める。[L,R](L,R<10^18)に含まれる周期的な整数の個数を求める問題。

解法

定石通り[1,X]に帰着させる。各長さごとにそれぞれ独立に考える。長さを固定すると、これは蟻本でも紹介されているメビウス関数を用いて数え上げることができる問題に帰着できる。

ACまでにかかった時間

60min程度。

acceptされたコード

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long int64;

const int moebius[] = {0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0, -1, -1, -1, 0, 0, 1, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, 1, 0, 0, 1, -1, -1, 0, 1, -1, -1, 0, -1, 1, 0, 0, 1};

int64 L, R;

void init() {
	cin >> L >> R;
}

int64 subSolve(int64 x) {
	if (x <= 1) {
		return 0;
	}
	int lg = 64 - __builtin_clzll(x);

	int64 ans = 0;
	for (int l = 2; l < lg; ++l) {
		for (int i = 1; i < l; ++i) if (l % i == 0) {
			ans -= (1<<(i-1)) * moebius[l/i];
		}
	}

	if ((x&(-x)) != x) {
		for (int i = 1; i < lg; ++i) if (lg % i == 0) {
			int iter = lg / i;
			int64 t = x >> ((iter-1) * i);
			int64 test = 0;
			for (int j = 0; j < iter; ++j) {
				test = (test << i) | t;
			}
			if (test > x) {
				--t;
			}
			if (t < (1<<(i-1))) {
				continue;
			}
			else {
				t ^= 1<<(i-1);
				++t;
			}
			ans -= t * moebius[lg/i];
		}
	}

	return ans;
}

int64 solve() {
	return subSolve(R) - subSolve(L-1);
}

int main() {
	init();
	cout << solve() << endl;
	return 0;
}