CodeChef submission 45120 (C++ 4.0.0-8) plaintext list. Status: AC, problem E4, contest JULY09. By jdmetz (Josh Metzler), 2009-07-02 06:49:10.
#include <cstdio>
#include <algorithm>
 
/* l = A*w + B
 * l*w+C  == 0   %P
 *
 *
 * (A*w^2 + B*w + C) ===  0  %P
 *
 * (-b +/- sqrt(b^2 - 4ac)) / (2a)
 *
 * (-B +/- sqrt(B*B - 4*A*C)) / (2*A))   %P
 *
 */
 
int minv(int n, int p) {
	int r0 = p, r1 = n, s0 = 1, s1 = 0, t0 = 0, t1 = 1, q1 = 0;
	while (r1) {
		int q2 = r0/r1;
		int r2 = r0%r1;
		int s2 = s0 - q1*s1;
		int t2 = t0 - q1*t1;
 
		r0 = r1; r1 = r2;
		q1 = q2;
		s0 = s1; s1 = s2;
		t0 = t1; t1 = t2;
	}
	return (s1+p)%p;
}
 
int mpow(long long n, int w, int p) {
	long long r = 1;
	for (int i = 0; w>>i; i++) {
		if ((w>>i)&1) r = (r*n)%p;
		n = (n*n)%p;
	}
	return (int)r;
}
 
bool euler(long long n, int p) {
	if (!n) return true;
	return mpow(n, (p-1)/2, p) == 1;
}
 
/* for non-0 n, either have 2 or 0 sqrts */
int msqrt(unsigned int n, unsigned int p, int &s1, int &s2) {
	s1 = -1; s2 = -1;
	if (!n) { s1 = 0; return 1; }
	if ((p&3) == 3) {
		s1 = mpow(n, (p+1)/4, p);
		s2 = p-s1;
		return 2;
	} else {
		int s = 0, q = p-1;
		while (!(q&1)) q >>= 1, s++;
		int nr = 2;
		while (euler(nr, p)) nr++;
		long long r = mpow(n, (q+1)/2, p);
		int v = mpow(nr, q, p), ni = minv(n, p);
		while (true) {
			int i = 0;
			long long r2n = r*r*ni%p;
			if (r2n == 1) break;
			do {
				r2n = (r2n*r2n)%p;
				i++;
			} while (i+1 < s && r2n != 1);
			r = r*mpow(v, 1<<(s-i-1), p)%p;
		}
		s1 = r;
		s2 = p-r;
		return 2;
	}
	return 0;
}
 
bool try2(int A, int B, int C, int x) {
	return !((A*x*x + B*x + C)&1);
}
 
int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		int A, B, C, P;
		scanf("%d %d %d %d", &A, &B, &C, &P);
 
		int ans[4], act = 0;
		if (P > 2) {
 /* (-B +/- sqrt(B*B - 4*A*C)) / (2*A))   %P */
 
			int B2 = ((long long)B)*B%P, AC4 = ((long long)A)*C%P*4%P;
			if (!euler((B2-AC4+P)%P, P)) {
				printf("0\n");
				continue;
			}
			int s1, s2;
			int sct = msqrt((B2-AC4+P)%P, P, s1, s2);
			long long i2A = minv(A*2%P, P);
	
			if (sct == 1) {
				ans[act++] = (s1-B+P)%P*i2A%P;
				ans[act++] = (-s1-B+P+P)%P*i2A%P;
			} else if (sct == 2) {
				ans[act++] = (s1-B+P)%P*i2A%P;
				ans[act++] = (-s1-B+P+P)%P*i2A%P;
				ans[act++] = (s2-B+P)%P*i2A%P;
				ans[act++] = (-s2-B+P+P)%P*i2A%P;
			}
			std::sort(ans, ans+act);
			for (int k = 1; k < act; k++) if (ans[k] == ans[k-1]) {
			for (int j = k+1; j < act; j++) ans[j-1] = ans[j];
				act--;
			}
		} else {
			if (try2(A, B, C, 0)) ans[act++] = 0;
			if (try2(A, B, C, 1)) ans[act++] = 1;
		}
		printf("%d", act);
		for (int j = 0; j < act; j++) printf(" %d", ans[j]);
		printf("\n");
	}
	return 0;
}