首页 > 代码库 > UVa 11121 - Base -2

UVa 11121 - Base -2

题目:计算以-2为基数的数的表示。

分析:数论。写出不同位数能表示的数字区间就可以找到规律。

            长度为1:[1,1]; 长度为2:[-2,-1]; 长度为3:[2,5];

            观察发现,区间长度增长为1,2,4,8,..,2^k,并且奇偶间隔开;

            这样可以按顺序找到对应的1的位置,每次减去对应的基底(-2^k)寻找下一个1的位置即可。

说明:又是数论。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

long long l[40],r[40],b[40];
int       ans[40];

int main()
{
	l[0] = 1; r[0] = 1; b[0] = 1;
	l[1] = -2;r[1] = -1;b[1] = -2;
	long long base = 4;
	for (int i = 2 ; i < 33 ; ++ i) {
		if (i%2) {
			r[i] = l[i-2]-1;
			l[i] = l[i-2]-base;
		}else {
			l[i] = r[i-2]+1;
			r[i] = r[i-2]+base;
		}
		base <<= 1;
		b[i] = b[i-1]*-2;
	}
	
	int n,m,s,e;
	while (~scanf("%d",&n))
	for (int i = 1 ; i <= n ; ++ i) {
		scanf("%d",&m);
		printf("Case #%d: ",i);
		
		for (int i = 0 ; i < 33 ; ++ i)
			ans[i] = 0;
		s = 32;
		while (s >= 0) {
			if (m >= l[s] && m <= r[s]) {
				ans[s] = 1;
				m -= b[s];
			}
			s --;
		}
		
		e = 32;
		while (e > 0 && !ans[e]) e --;
		while (e >= 0) printf("%d",ans[e --]);
		printf("\n");
	}
	return 0;
}


            

UVa 11121 - Base -2