UVA 1350 - Pinary(数论+递推）

#include <stdio.h>
#include <string.h>

int t, n, num[40], sum[40];

void init() {
	num[1] = num[2] = 1;
	sum[1] = 1; sum[2] = 2;
	for (int i = 3; i < 40; i++) {
		num[i] = num[i - 1] + num[i - 2];
		sum[i] = sum[i - 1] + num[i];
	}
}

int find(int n) {
	int l = 0, r = 40;
	while (l < r) {
		int mid = (l + r) / 2;
		if (sum[mid] >= n)
			r = mid;
		else
			l = mid + 1;
 	}
 	return l;
}

int main() {
	init();
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int len = find(n);
  		for (int i = len; i > 0; i--) {
  			if (n > sum[i - 1]) {
  				printf("1");
  				n = n - sum[i - 1] - 1;
     		}
     		else printf("0");
    	}
       	printf("\n");
 	}
	return 0;
}