CodeChef submission 51283 (C++ 4.0.0-8) plaintext list. Status: AC, problem E4, contest JULY09. By u2001137 (Neelesh), 2009-07-08 11:26:47.
#include <iostream>
using namespace std;
int A,B,C,P;
int ans1, ans2;
 
//return x such that a*x+b*y = 1 for some integer y
int extendedGCD(int a, int b)
{
  int x = 0, y = 1; 
  int lastx = 1, lasty = 0;
  while(b != 0)
    {
      int q = a/b;
      int temp = b; b = a % b; a = temp;
      temp = x; x = lastx - q*x; lastx = temp;
      temp = y; y = lasty-q*y; lasty = temp;
    }
  return lastx;
}
 
//Calculate b^s mod p
int powermodulo(int b, int s, int p)
{
  if(s == 1) return b%p;
  if(s == 0) return 1;
  int tr = int((long long)b*b % p);
  if(s % 2 == 0) return powermodulo(tr, s/2,p);
  return ((long long)b*powermodulo(tr,(s-1)/2,p))%p;
}
 
 
//solves x*x == a (mod p)
int solvequadratic(int a, int p)
{
  if(a > p) a = a%p;
  while(a < 0) a = a+p;
  if(a == 0)
    return 0;
  if(powermodulo(a,(p-1)/2,p) != 1)
      return -1;
 
  int n = 0, k = p-1;
  while(k % 2 == 0) 
      k/=2, n++;
  int q = 2;
  while(powermodulo(q,(p-1)/2,p) != (p-1))
    q++;
  int t = powermodulo(a,(k+1)/2,p);
  int r = powermodulo(a,k,p);
  while(true)
    {
      int s = 1;
      int i = 0;
      while(powermodulo(r,s,p) != 1)
	i+=1, s*=2;
      if(i == 0) 
	  return t; 
      int e = 1<<(n-i-1);
      int u = powermodulo(q, k*e,p);
      t = ((long long)t*u)%p;
      r = ((long long)r*u*u)%p;
    }
}
 
//solves ax == b (mod p)
int solvelinear(int  a, int  b, int p)
{
  if(a > p) a = a%p;
  while(a < 0) a = a+p;
 
  if(b > p) b = b%p;
  while(b < 0) b = b+p;
  
  if(b == 0) return 0;
  int x = extendedGCD(a,p);
  if(x > p) x = x%p;
  while(x < 0) x+=p;
  return int(((long long)b*x)%p);
}
 
 
void solve()
{
  ans1 = -1, ans2 = -1;
  if(B == C && C == 0)
    {
      ans1 = 0; return;
    }
  else if(P == 2)
    {
      if(C == 0) ans1 = 0;
      if((A + B + C)%P == 0) ans2 = 1;
      return;
    }
  else if(C == 0)
    {
      ans1 = 0;
      ans2 = solvelinear(A,P-B,P);
      return;
    }
  else if(B == 0)
    {
      int y = solvequadratic(((long long)A*(P-C))%P,P);
      if(y == -1) return;
      ans1 = solvelinear(A,y,P);
      if(y == 0) return;
      ans2 = solvelinear(A,P-y,P);
      return;
    }
  else
    {
      int y = solvequadratic(((long long)B*B-4LL*A*C)%P,P);
      if(y == -1) return;
      ans1 = solvelinear(int(2LL*A),y-B,P);
      if(y == 0) return;
      ans2 = solvelinear(int(2LL*A),P-y-B,P);
      return;
    }
      
}
 
int main()
{
  int T;
  scanf("%d",&T);
  for(int t = 1; t <= T; ++t)
    {
      scanf("%d%d%d%d", &A,&B,&C,&P);
      solve();
      if(ans1 == -1 && ans2 == -1) printf("0\n");
      else if(ans1 >= 0 && ans2 == -1) printf("1 %d\n", ans1);
      else if(ans2 >= 0 && ans1 == -1) printf("1 %d\n", ans2);
      else if(ans1 < ans2) printf("2 %d %d\n", ans1,ans2);
      else if(ans1 == ans2) printf("1 %d\n", ans1);
      else printf("2 %d %d\n", ans2, ans1);
    }
}