Cod sursa(job #919411)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 17:15:42
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> da,dc;
int abs(int a) {return a>0?a:-a;}
int sq(int a)
{
    int st,dr,med,last;
    st=0;dr=31680;last=0;
    while(st<=dr)
    {
        med=(st+dr)/2;
        if(med*med<=a) {last=med;st=med+1;}
        else dr=med-1;
    }
    return last;
}
void afis(int p1,int q1,int p2,int q2)
{
    printf("(");
    if(p1==-1) printf("-");
    else if(p1!=1) printf("%d",p1);
    printf("x");
    if(q1>=0) printf("+%d",q1);
    else printf("%d",q1);
    printf(")(");
    if(p2==-1) printf("-");
    else if(p2!=1) printf("%d",p2);
    printf("x");
    if(q2>=0) printf("+%d",q2);
    else printf("%d",q2);
    printf(")\n");
}
void solve(int a,int b,int c,int k)
{
    int lim,d;
    da.clear();dc.clear();
    lim=sq(abs(a));
    if(lim*lim!=a && lim*lim!=-a) lim++;
    for(d=1;d<lim;d++)
        if(a%d==0)
        {
            da.push_back(d);
            da.push_back(a/d);
            da.push_back(-d);
            da.push_back(-a/d);
        }
    if(lim*lim==a || lim*lim==-a) {da.push_back(lim);da.push_back(-lim);}
    lim=sq(abs(c));
    if(lim*lim!=c && lim*lim!=-c) lim++;
    for(d=1;d<lim;d++)
        if(c%d==0)
        {
            dc.push_back( d  );
            dc.push_back( c/d);
            dc.push_back(-d  );
            dc.push_back(-c/d);
        }
    if(lim*lim==c) {dc.push_back(lim);dc.push_back(-lim);}
    sort(da.begin(),da.end());
    sort(dc.begin(),dc.end());
    vector<int>::iterator P1,Q1;int nr=0;
    for(P1=da.begin();P1!=da.end();P1++)
        for(Q1=dc.begin();Q1!=dc.end();Q1++)
            if((*P1) * (c / (*Q1)) + (a / (*P1)) * (*Q1) == b)
            {
                nr++;
                if(nr==k)
                {
                    afis(*P1,*Q1,a/(*P1),c/(*Q1));
                    return;
                }
            }
    printf("-1\n");
}
int main()
{
    freopen("ecuatie.in","r",stdin);
    freopen("ecuatie.out","w",stdout);
    int d,lim,a,b,c,k;
    while(scanf("%d%d%d%d",&a,&b,&c,&k)==4)
        solve(a,b,c,k);
    return 0;
}