Artifact Content
Not logged in

Artifact e21b6366bf8728d909d8ce92c75ec4634a173022


#############################################################################
# Written in
#    Blue 1.7.5
#    http://www.lechak.info/blue/
#############################################################################

global FROM_STRING = func {
	arg s;

	a = [];
	i = 0;
	loop {
		a = a.append( s.substr(i,i+1).num() );
		(i=i+1) >= s.length() ? return;
	};
	return a;
};

global TO_STRING = func {
	arg x;
	lexical s = "";
	x.map( func{ s = s + this; } );
	return s;
};

global LESS = func {
	arg x;
	arg y;

	xl = x.length();
	yl = y.length();
	(xl < yl) ? return 1;
	(xl > yl) ? return 0;
	i = 0;
	return loop {
		(i == xl)     ? return 0;
		(x[i] < y[i]) ? return 1;
		(x[i] > y[i]) ? return 0;
		i = i+1;
	};
};

global SUB = func {
	arg x;
	arg y;

	x.length() > y.length() ? (y = [].resize(x.length()-y.length(),0).merge(y));
	z = [].resize(x.length(), 0);
	i = x.length()-1;
	carry = 0;
	loop {
		z[i]  = x[i] - y[i] - carry;
		carry = z[i] < 0 ? (z[i]=z[i]+10; 1) : 0;
		(i=i-1) < 0 ? return;
	};
	head = 0;
	loop {
		head == z.length()-1 ? return;
		z[head] != 0 ? return;
		head = head + 1;
	};
	return z.slice(head, z.length());
};

global DBL = func {
	arg x;

	z = [].resize(x.length(), 0);
	i = x.length()-1;
	carry = 0;
	loop {
		z[i]  = x[i] + x[i] + carry;
		carry = z[i] > 9 ? (z[i]=z[i]-10; 1) : 0;
		((i=i-1) < 0) ? return;
	};
	return (carry==1 ? [1].merge(z) : z);
};

global DIF = func {
	arg x;
	arg y;
	return LESS(x, y) ? SUB(y, x) : SUB(x, y);
};

global MOD = func {
	arg x;
	arg y;

	LESS(x,y) ? return x;
	z = MOD(x, DBL(y));
	LESS(z,y) ? return z;
	return SUB(z,y);
};

global ISZERO = func {
	arg x;
	return x[0] == 0;
};

global GCD = func {
	arg x;
	arg y;
	return ISZERO(x) ? y : GCD(MOD(y,x),x);
};

#############################################################################

solve = func {
	arg N;
	arg t;
	t = t.map( func{return FROM_STRING(this);} );

	lexical t0 = t[0];
	lexical g  = DIF(t0, t[1]);
	t.slice(2, t.length()).map(func{
		g = GCD(g, DIF(t0, this));
	});
	r = MOD(t[0], g);
	return TO_STRING( ISZERO(r) ? r : DIF(g,r) );
};

input = sys.library("streams").stdio().read(1000000000).split("\n").map(func{return this.split(" ");});
C = input[0][0].num();

CaseID = (args.length() >= 2 ? args[1].num() : 1);
loop {
	"Case #".print();
	CaseID.print();
	": ".print();
	solve( input[CaseID][0].num(), input[CaseID].slice(1,input[CaseID].length()) ).print();
	"\n".print();
	((CaseID = CaseID+1) > C) ? return;
};