Ecuatie

Dupa cum bine stim de la matematica putem rescrie o ecuatie Ax2+Bx+C ca A(x-x1)(x-x2) unde x1,x2 sunt solutiile ecuatiei. Acestea se pot determina astfel:

  • Fie delta = b2-4ac
  • x1 = (-b-√delta)/2a
  • x2 = (-b+√delta)/2a

Este evident ca o prima condite ca sa putem rescrie ecuatia sub forma (P1x+Q1)(P2x+Q2) unde P1,P2,Q1,Q2 sunt numere intregi este ca delta sa fie patrat perfect.
Din cele mai sus putem deduce ca:
(P1x+Q1)(P2x+Q2) = P1P2(x+Q1/P1)(x+Q2/P2) = A(x-x1)(x-x2)
Este imediat evident ca P1 trebuie sa fie un divizor al numarului A. Vom lua astfel fiecare divizor d al numarului A (atentie la semn! pentru 2 se vor lua valorile 1,-1,2,-2) si vom atribui urmatoarele valori:

  • P1 = d
  • Q1 = -x1*d
  • P2 = A/d
  • Q2 = -x2*(A/d)
  • P1 = d
  • Q1 = -x2*d
  • P2 = A/d
  • Q2 = -x1*(A/d)
Un divizor d se considera bun doar daca Q1,Q2 sunt numere intregi (atentie, x1 si x2 nu trebuie neaparat sa fie numere intregi ca sa existe solutii!). Astfel, putem genera toate solutiile intr-un vector, pe care le putem apoi sorta dupa P1 respectiv Q1 si vom afisa a K-a solutie din vector.
Pentru a genera toti divizorii numarului A in complexitate O(√A) vom folosi urmatorul algoritm:
pentru d = 1, sqrt(|A|):
    daca A%d = 0:
        d, -d, A/d, -A/d sunt divizori

O metoda simpla pentru a evita generarea aceleiasi solutii de mai multe ori (de exemplu in cazurile in care d = A/d sau x1 = x2) este eliminarea duplicatelor din vectorul de solutii inainte sa afisam rezultatul.