Четвёртый открытый Зеленоградский турнир 2008

#include <stdio.h>
#include <string.h>
#define u64 unsigned long long
char buf[1000001];
unsigned c13[15015];
unsigned c23[7429];
unsigned c31[33263];
unsigned ex[] = {
530714887,20647621,253893397,851703301,1452201241,413778817,611812321,862678081,396271,
437247841,145206361,1419575167,1223941657,1528936501,91433281,32899201,977483449,36307981,
437289029,351058753,1729884511,188985961,25457833,1105779277,631974613,523756711,
1873177693,734166217,96791881,1415969101,796200901,719256497,1058575981,498706651,
200753281,2147022749,7295851,1568471813,706728377,1108135381,37109467,6617929,6868261,
792145729,24214051,1516071547,434042801,178956971,77533123,705351583,100017223,
1272866167,14282143,145348529,638837761,9591661,388695301,1217924159,898343713,1406851249,
36861901,474983881,115873801,1603810561,1511558533,548989561,680972909,464826781,
946787377,160672201,462639409,7759937,73522051,681019921,759266621,20140129,1549308001,
1704682753,732805681,1821792457,201646801,61754941,1150229761,1510870241,252853921,
1381243709,15978007,897087361,2100292841,1204205449,1407548341,976396961,149069989,
224136013,38439523,587861,288099001,1312573123,630888481,1352531269,304080001,207030541,
266811169,373012777,170640961,1534063081,13838569,1336210313,17375249,658831741,1020220661,
420607441,26758057,6334351,848755969,1567830241,317137969,631767943,129461617,35820937,
161498681,897842401,1565893201,615344227,1845128533,899019353,637907581,64377991,1604440111,
47744209,330396701,2072624761,34003061,1223884969,353815801,1348964401,914906539,565707061,
643316461,366652201,841402801,12498061,514738981,557437999,536870911,476011901,903108821,2};
u64 p2[64];
const u64 p32 = ((u64)1)<<32;
int main()
{
	//freopen("output.txt", "w", stdout);
	u64 x_v = 1;
	p2[0] = 1;
	for(int i = 1; i != 64; ++i)
		p2[i] = (x_v<<=1);
	for(int i = 0; i != 15015; i += 3)
		c13[i] = true;
	for(int i = 5; i != 15020;)
	{
		c13[i] = true;
		c13[i+=5] = true;
		i+=10;
	}
	for(int i = 0; i != 15015; i += 7)
		c13[i] = true;
	for(int i = 0; i != 15015; i += 11)
		c13[i] = true;
	for(int i = 0; i != 15015; i += 13)
		c13[i] = true;
	for(int i = 0; i != 7429; i += 17)
		c23[i] = true;
	for(int i = 19; i != 7429; i += 19)
		c23[i] = true;
	for(int i = 23; i != 7429; i += 23)
		c23[i] = true;
	for(int i = 0; i != 33263; i += 29)
		c31[i] = true;
	for(int i = 31; i != 33263; i += 31)
		c31[i] = true;
	for(int i = 37; i != 33263; i += 37)
		c31[i] = true;
	unsigned a = 1;
	int j = 1;
	unsigned counter = 0;
	int r = 1, d = 1234567890%15015;
	int f = d + 15015 - 0x80000000%15015;
	buf[1000001]='\0';
	for(int i = 0; i != 18; ++i)
	{
		memset(buf, '0', 1000000);
		for(; j != 1000000; ++j)
		{
			a += 1234567890;
			if(a & 0x80000000)
			{
				r += f;
				a &= 0x7FffFFff;
			}else
				r += d;
			if(r >= 15015)
				r+=-15015;
			if(c13[r])
				continue;
			if(c23[a%7429])
				continue;
			if(c31[a%33263])
				continue;
			unsigned p = a;
			unsigned result = p2[(--p)&0x3f]%a;
			p>>=6;
			u64 x = p32;
			x%=a;
			x<<=32;
			x%=a;
			while(p)
			{
				if(p&1)
					result=(x*result)%a;
				x *= (unsigned)x;
				x %= a;
				p>>=1;
			}
			if(result != 1)
				continue;
			if(a == ex[counter])
			{
				++counter;
				continue;
			}
			buf[j] = '1';
		}
		printf("%s", buf);
		j = 0;
	}
	return 0;
}