2103.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2103 on 2006-03-15 at 21:06:31 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 102400;

int main()
{
	long long i, p;
	bool bit[MAX];

	while(scanf("%lld", &p) != EOF && p != 0) {
		memset(bit, false, sizeof(bit)); int on = 0;
		for(i = 1; i < p; i++)
			if(!bit[(i*i-1)%p]) { bit[(i*i-1)%p] = true; on++; }
		if(on != (p-1)/2) printf("Impossible");
		else for(i = 0; i < p-1; i++) putchar(bit[i] ? '0' : '1');
		putchar('\n');
	}
	
	return 0;
}