Numarul descompus in factori primi sa zicem ca arata ceva de forma asta:
[tex]N=x_{1}^{a1}*x_{2}^{a2}*x_{3}^{a3}*,,,*x_{n}^{an}[/tex] unde x1,x2,..xn sunt numere prime si a1,a2,a3...an sunt puterile lor.
acum, tu vrei sa gasesti toate numerele de forma [tex]LCM(P.Q)=N[/tex]
Sa zicem ca am avea o despartire a lui P in factori primi ca cea pentru N.
Daca presupui ca factorul xi are o putere j care este mai mica decat ai
[tex]0\leqslant j\leqslant a_{i}[\tex]
atunci inseamna ca in factorizarea lui Q, xi va avea ca exponent pe ai, altfel nu ai mai obtine multiplul comun ca fiind N. In calculul multiplului comun se iau toate elementele comune si necomune la cele mai mari puteri existente. Deci, unul dintre factorii primi trebuie sa aiba puterea la cea care se afla in N.
Daca gandesti la fel pentru Q, exista un element k care este puterea factorului prim xi si este mai mic decat ai
[tex]0\leqslant k\leqslant a_{i}[\tex]
atunci in factorizarea lui P trebuie sa existe factorul prim xi la puterea ai
In fiecare dintre cele doua cazuri, poti sa combini numerele j-k, care pot fi in total (ai+1) elemente, deci reies la final (2i+1) combinatii posibile, cu una scazuta pentru cazul i=k
Fiind o singura putere, daca consideri combinatiile pentru toate puterile, si cum aceste puteri sunt ale unor numere inmultite, numarul final de combinatii va fi:
[tex]N_{pairs}=(2a_{1}+1)*(2a_{2}+1)*(2a_{3}+1)*...*(2a_{n}+1)\tex]
De exemplu, daca ai 500=2^{2}*5^{3}, ai urmatoarele cazuri pentru puteri
2^0 2^2
2^1 2^2
2^2 2^2
2^2 2^1
2^2 2^0
5^0 5^3
5^1 5^3
5^2 5^3
5^3 5^3
5^3 5^2
5^3 5^1
5^3 5^0
Si acum avem fiecare dintre aceste cazuri combinate. Cum sunt doua multimi cu cardinale(nr de elemente pe set): 5 respectiv 7, avem atunci
Numar perechi=5*7=35
Am adaugat fisierul cu programul C++
