h2(#divizori). Problema 4: _Divizori_

Vom considera un numar natural $N$. In sirul $A$ vom aseza toti divizorii lui $N (2 <= N <= 2.000.000.000)$. Se cere sa se permute elementele sirului $A$ astfel incat pentru oricare doua elemente consecutive $A[i]$ si $A[i+1]$ sa avem fie $A[i] = A[i+1] * p$, fie $A[i+1] = A[i] * p$ ( $p$ numar prim oarecare). Valoarea $p$ poate diferi de la o pereche de elemente la alta. De exemplu, pentru $N = 12$ o posibila solutie ar fi $1, 2, 3, 4, 12, 6, 3$.

Vom considera un numar natural $N$. In sirul $A$ vom aseza toti divizorii lui $N (2<=N<=2.000.000.000)$. Se cere sa se permute elementele sirului $A$ astfel incat pentru oricare doua elemente consecutive $A[i]$ si $A[i+1]$ sa avem fie $A[i]=A[i+1]*p$, fie $A[i+1]=A[i]*p$ ( $p$ numar prim oarecare). Valoarea $p$ poate diferi de la o pereche de elemente la alta. De exemplu, pentru $N = 12$ o posibila solutie ar fi $1, 2, 3, 4, 12, 6, 3$.

h3. Rezolvare
Numarul $N$ are maxim $2*N^1/2^$ divizori. Descompunerea lui $N$ in factori primi are forma $P{~1~}^E{~1~}^ * P{~2~}^E{~2~}^ * ... * P{~k~}^E{~k~}^$ ( $P{~1~}, P{~2~}, ..., P{~k~}$ - numere prime, si $E{~i~} &isin; _**N**_, E{~i~} &gt; 0$ ). Un divizor al lui $N$ va fi reprezentat printr-un vector de exponenti $(e{~1~}, e{~2~}, ..., e{~k~})$ unde $0<=e{~i~}<=E{~k~}$. Prin urmare, problema noastra poate fi usor redusa la urmatoarea cerinta: ordonati toti vectorii $(e{~1~}, e{~2~}, ..., e{~k~})$ intr-un sir cu proprietatea ca diferenta intre doi vectori consecutivi se realizeaza la o singura pozitie a vectorilor si cele doua elemente ale vectorilor de pe pozitia respectiva difera prin o unitate.
Exemplul din enuntul problemei se poate reprezenta astfel:
$1, 2, 4, 12, 6, 3$

$P{~1~} = 2 E{~1~} = 2$
$P{~2~} = 3 E{~2~} = 1$

$P{~1~}=2 E{~1~}=2$
$P{~2~}=3 E{~2~}=1$

$(0,0), (1,0), (2,0), (2,1), (1,1), (0,1)$
Aceasta problema este o generalizare a determinarii codului Gray si poate fi rezolvata generalizand metoda expusa mai sus. Presupunem ca stim sa generam o solutie pentru $M = N/(P{~k~}E{~k~})$ (o solutie pentru un numar cu $k-1$ factori primi). Sa vedem cum generam o solutie pentru $N$. Fie $C$ vectorul solutie pentru $M$ si $R$ vectorul $C$ inversat. O solutie poate fi: