Cod sursa(job #1505013)

Utilizator akaprosAna Kapros akapros Data 18 octombrie 2015 17:31:51
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define maxN 100002
using namespace std;
int k, i, j;
ll x1, x2, delta, a, b, c, sol;
ll p1, p2, q1, q2, rd;
struct ec
{
    ll x;
    ll y;
    ll z;
    ll t;
} v[maxN];
int cmp(const ec a, const ec b)
{
    if (a.x == b.x)
        return -a.z < -b.z;
    return a.x < b.x;
}
void read()
{
    int rd;
    freopen("ecuatie.in", "r", stdin);
    scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
}
void write(int sol)
{
    freopen("ecuatie.out", "w", stdout);
    if (sol == -1 || k > sol)
        printf("%d", -1);
    else
    {
        sort(v + 1, v + sol + 1, cmp);
        printf("(");
        if (v[k].x == -1)
            printf("-");
        if (abs(v[k].x) == 1)
            printf("x");
        else
            printf("%lldx", v[k].x);
        if (v[k].z > 0)
            printf("-");
        else
            printf("+");
        printf("%lld)", abs(v[k].z));

        printf("(");
        if (v[k].y == -1)
            printf("-");
        if (abs(v[k].y) == 1)
            printf("x");
        else
            printf("%lldx", v[k].y);
        if (v[k].t > 0)
            printf("-");
        else
            printf("+");
        printf("%lld)", abs(v[k].t));
    }
}
void ecu(ll p1, ll p2)
{
    if (((-b + rd) * p1) % (2 * a) == 0 && ((-b - rd) * p2) % (2 * a) == 0)
    {
        q1 = ((-b + rd) * p1) / (2 * a);
        q2 = ((-b - rd) * p2) / (2 * a);
        v[++ sol].x = p1;
        v[sol].y = p2;
        v[sol].z = q1;
        v[sol].t = q2;
    }
    if (rd > 0 && ((-b + rd) * p2) % (2 * a) == 0 && ((-b - rd) * p1) % (2 * a) == 0)
    {
        q1 = ((-b + rd) * p2) / (2 * a);
        q2 = ((-b - rd) * p1) / (2 * a);
        {
            v[++ sol].x = p1;
            v[sol].y = p2;
            v[sol].z = q2;
            v[sol].t = q1;
        }
    }
}
void solve()
{
    delta = (b * b - 4 * a * c) * 1LL;
    if (delta >= 0)
        rd = ((ll)(sqrt(delta)));
    if (rd * rd * 1LL != delta)
    {
        write(-1);
        exit(0);
    }

    for (p1 = 1; p1 * p1 <= abs(a); ++ p1)
        if (!(a % p1))
        {
            p2 = a / p1;
            ecu(p1, p2);
            ecu(-p1, -p2);
            if (abs(p1) != abs(p2))
            {
                ecu(p2, p1);
                ecu(-p2, -p1);
            }
        }
}
int main()
{
    read();
    solve();
    write(sol);
}