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:
|
|
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.