Cod sursa(job #330190)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 iulie 2009 09:01:26
Problema Ecuatie Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.84 kb
# include <stdio.h>
# include <stdlib.h>
# include <math.h>

typedef struct NOD 
        {
        long long p1,q1,p2,q2;
        };
        
NOD t,v[100000];
long int ciur[30000],ciurlen,fact[30000],expo[30000],factlen,vlen;

int compara_NOD(const void *aa, const void *bb)
{
    NOD *a,*b;
    a=(NOD*)aa;
    b=(NOD*)bb;
    if (a->p1<b->p1) return -1;
    if (a->p1>b->p1) return 1;
    if (a->q1<b->q1) return -1;
    if (a->q1>b->q1) return 1;
    return 0;
}

long long cmmdc(long long a, long long b)
{
     if (a<0) a*=-1;
     if (b<0) b*=-1;
     long long aux; 
     if (a<b) {aux=a;a=b;b=aux;}
     long long r=a%b;
     while (r)
           {
           a=b;b=r;r=a%b;
           }
     return b;
}

void scrie(FILE *g, NOD *a)
{
     fprintf(g,"(");
     if (a->p1==1) fprintf(g,"x");
     else if (a->p1==-1) fprintf(g,"-x");
     else fprintf(g,"%lldx",a->p1);
     if (a->q1>0) fprintf(g,"+%lld)",a->q1);
     else fprintf(g,"%lld)",a->q1);
     
     fprintf(g,"(");
     if (a->p2==1) fprintf(g,"x");
     else if (a->p2==-1) fprintf(g,"-x");
     else fprintf(g,"%lldx",a->p2);
     if (a->q2>0) fprintf(g,"+%lld)",a->q2);
     else fprintf(g,"%lld)",a->q2);
     
     fprintf(g,"\n");
}    

void genereaza_ciur(long long a)
{
     long long lim=(long long)sqrt(a)+1;
     ciurlen=1;
     ciur[1]=2;
     long int i,j,prim;
     for (i=3;i<lim;i+=2)
         {
         //verif daca i e prim;
         prim=1;
         for (j=1;j<=ciurlen;j++)
             {
             if (ciur[j]>sqrt(i)) break;
             if (i%ciur[j]==0) 
                {
                prim=0;
                break;
                }
             }
         if (prim) ciur[++ciurlen]=i;
         }
}

void factorizeaza(long long a)
{
     int j;
     for (j=1;a!=1&&j<=ciurlen;j++)
         {
         if (a%ciur[j]==0)
            {
            factlen++;
            fact[factlen]=ciur[j];
            while (a%ciur[j]==0)
                  {
                  expo[factlen]++;
                  a/=ciur[j];
                  }
            }
         }
     if (a!=1)
        {
        fact[++factlen]=a;
        expo[factlen]=1;
        }
}

void genereaza_tuple(long int prod,long int a,long int nivel,long long delta)
{
     long int i,pow;
     for (i=0,pow=1;i<=expo[nivel];i++,pow*=fact[nivel])
         if (nivel<factlen)
            genereaza_tuple(prod*pow,a,nivel+1,delta);
         else
             {
                                                      
             vlen++;
             v[vlen].p1=t.p1*prod*pow;
             v[vlen].p2=t.p2*(a/(prod*pow));
             v[vlen].q1=t.q1*prod*pow;
             v[vlen].q2=t.q2*(a/(prod*pow));
             
             if (delta)
             {
             vlen++;
             v[vlen].p2=t.p1*prod*pow;
             v[vlen].p1=t.p2*(a/(prod*pow));
             v[vlen].q2=t.q1*prod*pow;
             v[vlen].q1=t.q2*(a/(prod*pow));
             }
             
             vlen++;
             v[vlen].p1=-t.p1*prod*pow;
             v[vlen].p2=-t.p2*(a/(prod*pow));
             v[vlen].q1=-t.q1*prod*pow;
             v[vlen].q2=-t.q2*(a/(prod*pow));
             
             if (delta)
             {
             vlen++;
             v[vlen].p2=-t.p1*prod*pow;
             v[vlen].p1=-t.p2*(a/(prod*pow));
             v[vlen].q2=-t.q1*prod*pow;
             v[vlen].q1=-t.q2*(a/(prod*pow));
             }
             }
}                         

int main()
{
    FILE *g=fopen("ecuatie.out","w");
    //citirea
    long int a,b,c,k;
    FILE *f=fopen("ecuatie.in","r");
    fscanf(f,"%ld%ld%ld%ld",&a,&b,&c,&k);
    fclose(f);
    //calculam
    long long delta=(long long)b*b-(long long)4*a*c;
    long long raddelta=(long long)sqrt(delta);
    long long x1f=(long long)-b-raddelta;
    long long x2f=(long long)-b+raddelta;
    long long x1rem=2*a;
    long long x2rem=2*a;
    long long cmm1=cmmdc(x1f,x1rem);
    long long cmm2=cmmdc(x2f,x2rem);  
    x1f/=cmm1;x1rem/=cmm1;
    x2f/=cmm2;x2rem/=cmm2;
    a/=x1rem;a/=x2rem;
           //acum am obtinut: a*(x1rem*X-x1f)*(x2rem*X-x2f)
           //de acuma tre' sa factorizam a, sa sortam si sa punem al k-lea tuplu
    t.p1=x1rem;t.q1=-x1f;t.p2=x2rem;t.q2=-x2f;
    genereaza_ciur(a);
    factorizeaza(a);
    genereaza_tuple(1,a,1,delta);
    genereaza_tuple(-1,a,1,delta);
    qsort(v+1,vlen,sizeof(NOD),compara_NOD);
    //tre' sa elimini dublele    
    long int i,no;
    i=1;no=0;
    while (i<=vlen&&no<k)
          {
          if (i-1==0||compara_NOD(&v[i],&v[i-1])!=0)
             no++;
          if (no==k) break;
          i++;
          }
//    for (i=1;i<=vlen;i++)
//        scrie(stdout,&v[i]);
//    getchar();
    
    if (i>vlen) fprintf(g,"-1\n");
    else scrie(g,&v[i]);
    fclose(g);
    
    return 0;
}