Cod sursa(job #340624)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 15 august 2009 19:23:19
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long i64;
#define pb push_back
#define mp make_pair
#define mPQ(x,y,z,t) mp(mp(x,y),mp(z,t))
int A,B,C,K,P1,Q1,P2,Q2;
i64 cmmdc(i64 x,i64 y) 
{
    if (!y) return x;
    return cmmdc(y,x%y);
}
int d[16],e[16],ND;
vector<int> Div;
void back(int k,int x)
{
     if (k==ND+1) 
     {
        Div.pb(x);
        return;
     }
     int i,y=x;
     for (i=0;i<=e[k];++i)
     {
       back(k+1,y);
       y*=d[k];
     }
}
i64 p1,q1,p2,q2;
typedef pair< pair<int,int> , pair<int,int> > PQ;
vector<PQ> V;
int main()
{
    freopen("ecuatie.in","r",stdin);
    freopen("ecuatie.out","w",stdout);
    scanf("%d %d %d %d",&A,&B,&C,&K);
    //calculez delta
    i64 delta=(i64)B*B-(i64)4*A*C;
    if (delta<0) {printf("-1");return 0;}
    i64 l=0,r=2147483647,x,rad=0;
    while (l<=r)
    {
          x=(l+r)/2;
          if (x*x<=delta) rad=x,l=x+1;
          else r=x-1;
    }
    if (rad*rad != delta) {printf("-1");return 0;}
    //rescriu ecuatia sub forma A'(p1X+q1)(p2X+q2) cu (p1,q1)=(p2,q2)=1
    int n=2*A;
    q1=rad-B;p1=n;
    r=cmmdc(p1,q1);
    q1/=r;p1/=r;
    A/=p1;
    p2=n;q2=-rad-B;
    r=cmmdc(p2,q2);
    p2/=r;q2/=r;
    A/=p2;
    q1=-q1;q2=-q2;
    //descompun pe A' in factori primi
    int i,k=0;
    n=A;
    if (n<0) n=-n;
    if (n%2 == 0) 
      {
          k=0;
          while (n%2 == 0) n/=2,++k;
          d[++ND]=2;e[ND]=k;
      }
    for (i=3;i*i <=n ;i+=2)
      if (n%i ==0)
      {
         k=0;
         while (n%i == 0) n/=i,++k;
         d[++ND]=i;e[ND]=k;
      }
    if (n>1) d[++ND]=n,e[ND]=1;
    //generez toti divizorii lui A'
    back(1,1);    
    //generez toate scrierile posibile
    for (i=0;i<(int)Div.size();++i)
    {
        l=Div[i];r=A/Div[i];
        V.pb(mPQ(p1*l,q1*l,p2*r,q2*r));
        l=-l;r=-r;
        V.pb(mPQ(p1*l,q1*l,p2*r,q2*r));
        swap(p1,p2);swap(q1,q2);
        V.pb(mPQ(p1*l,q1*l,p2*r,q2*r));
        l=-l;r=-r;
        V.pb(mPQ(p1*l,q1*l,p2*r,q2*r));
    }
    //sortez si elimin duplicatele
    sort(V.begin(),V.end());  
    int NR=unique(V.begin(),V.end())-V.begin();  
    if (K > NR) {printf("-1");return 0;}
    //afisam solutia 
    k=K-1;
    P1=V[k].first.first;
    Q1=V[k].first.second;
    P2=V[k].second.first;
    Q2=V[k].second.second;
    
    printf("(");
    if (P1<0) printf("-"),P1=-P1;
    if (P1>1) printf("%d",P1);
    printf("x");
    if (Q1<0) printf("-"),Q1=-Q1;
    else printf("+");
    printf("%d)(",Q1);
    if (P2<0) printf("-"),P2=-P2;
    if (P2>1) printf("%d",P2);
    printf("x");
    if (Q2<0) printf("-"),Q2=-Q2;
    else printf("+");
    printf("%d)",Q2);
    return 0;
}