UVA 11645 - Bits(數論+計數問題)

題目鏈接：11645 - Bits

題意：給定一個數字n，要求0-n的二進制形式下，連續11的個數。 思路：和 UVA 11038 這題類似，枚舉中間，然後處理兩邊的情況。 不過本題最大的答案會超過longlong，要用高精度，不過借鑒http://www.cnblogs.com/TO-Asia/p/3214706.html這個人的方法，直接用兩個數字來保存一個數字，這樣能保存到2個longlong的長度，就足夠存放這題的答案了。 代碼：

#include 
#include 

long long n, a, b;
const long long DIG = 1e13;
void add(long long num) {
	b += num;
	a += b / DIG;
	b %= DIG;
}

int main() {
	int cas = 0;
	while (~scanf("%lld", &n) && n >= 0) {
		a = b = 0;
		long long tmp = n, d = 1;
		while (n > 1) {
			add((n>>2) * d);
			if ((n&3) == 3)
				add((tmp&(d - 1)) + 1);
			d <<= 1;
			n >>= 1;
		}
		printf("Case %d: ", ++cas);
		if (a) {
  			printf("%lld", a);
  			printf("%013lld\n", b);
		}
		else printf("%lld\n", b);
 	}
	return 0;
}