Cerința
Gigel a învăţat la matematică despre cel mai mic multiplu comun a două numere şi acum trebuie să determine pentru fiecare valoare x dintr-un set de valori date câte perechi ordonate de numere naturale (a,b) au cel mai mic multiplu comun x.
Date de intrare
Programul citește de la tastatură număr n, apoi n valori x.
Date de ieșire
Programul va afișa pe ecran n valori, separate prin exact un spaţiu; fiecare valoare afișată reprezintă numărul de perechi care au cel mai mic multiplu comun egal cu valoarea x corespunzătoare.
Restricții și precizări
1 ≤ n ≤ 1.000
1 ≤ x ≤ 2.000.000.000
Exemplu
Intrare
2
12 4
Ieșire
15 5
Explicație
Cele 15 perechi pentru care cel mai mic multiplu comun este 12 sunt: (1,12), (2,12), (3,4), (3,12), (4,3), (4,6), (4,12), (6,4), (6,12), (12,1), (12,2), (12,3), (12,4), (12,6), (12,12).
Răspunsuri la întrebare
Răspuns de
12
Numarul descompus in factori primi sa zicem ca arata ceva de forma asta:
unde x1,x2,..xn sunt numere prime si a1,a2,a3...an sunt puterile lor.
acum, tu vrei sa gasesti toate numerele de forma
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++
acum, tu vrei sa gasesti toate numerele de forma
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++
Anexe:
Alte întrebări interesante
Matematică,
8 ani în urmă
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Biologie,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă