Cod sursa(job #110178)

Utilizator HemorrhageMocanu Tiberiu Hemorrhage Data 25 noiembrie 2007 19:41:51
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#include <math.h>

       long a, b, c ,k;
       long da [1001], dc [1001];

 void div (long x, long dx [])
	 {
	     int r=sqrt (labs (x)), i;
	     for (i=1; i<=r; i++)
		  if (x % i == 0)
		      {
			 dx [++dx [0]]=i;
			 dx [++dx [0]]=x/i;
			 dx [++dx [0]]=-1*i;
			 dx [++dx [0]]=-1*x/i;
		      }
	     if (r*r == x)
		 dx [0]--;
	 }

 int partitie (int st, int dr, long d [])
	     {
		int i, j, m;
		long piv, aux;
		i=st-1;
		j=dr+1;
		m=(st+dr)/2;
		piv=d [m];
		while (1)
		     {
			do {i++;} while (d [i] < piv);
			do {j--;} while (d [j] > piv);
			if (i < j)
			  {
			      aux=d [i];
			      d [i]=d [j];
			      d [j]=aux;
			  }
			   else
				 return j;
		     }
	     }

 void quicks (int st, int dr, long d [])
	    {
		int p;
		if (st < dr)
		  {
		     p=partitie (st, dr, d);
		     quicks (st, p, d);
		     quicks (p+1, dr, d);
		  }
	    }

 void printp (long a)
	   {
	       if (a == -1)
		   printf ("-");
		 else
		      if (a != 1)
			  printf ("%ld", a);
	       printf ("x");
	   }

 void printq (long a)
	   {
	       if (a < 0)
		   printf ("%ld", a);
		 else
		      printf ("+%ld", a);
	   }

 int ecuatie ()
	     {
		 long i;
		 int ok, p1=0, p2=0;
		 for (i=1; i<=k; i++)
		    {
		       ok=1;
		       while (ok)
			    {
				p2++;
				if (p2 > dc [0])
				    {
				       p1++;
				       p2=1;
				    }
				if (p1 > da [0])
				    return 0;
				if (da [p1] * dc [p2] + a/da [p1] * c/dc [p2] == b)
				    ok=0;
			    }
		    }
		 printf ("(");
		 printp (da [p1]);
		 printq (dc [p2]);
		 printf (")(");
		 printp (a/da [p1]);
		 printq (c/dc [p2]);
		 printf (")");
		 return 1;
	     }

 int main ()
	 {
	     freopen ("ecuatie.in", "r", stdin);
	     freopen ("ecuatie.out", "w", stdout);
	     scanf ("%ld %ld %ld %ld", &a, &b, &c, &k);
	     div (a, da);
	     div (c ,dc);
	     quicks (1, da [0], da);
	     quicks (1, dc [0], dc);
	     if (ecuatie () == 0)
		 printf ("-1");
	     fcloseall ();
	     return 0;
	 }