Raul: Pagină nouă: = Cerința = Numim factorul-x a `2` numere produsul tuturor factorilor primi comuni și diferiți ai celor `2` numere. Se dau `n` numere naturale distincte. Se cere să se afle câți factori-x diferiți pot fi obținuți din toate perechile diferite de numere din șir și să se afișeze aceștia. = Date de intrare = Fișierul de intrare `factorulx.in` conține pe prima linie numărul `n`, iar pe a doua linie `n<...`


2023-12-14T13:42:28Z
Pagină nouă:  = Cerința = Numim factorul-x a <code>2</code> numere produsul tuturor factorilor primi comuni și diferiți ai celor <code>2</code> numere.  Se dau <code>n</code> numere naturale distincte. Se cere să se afle câți factori-x diferiți pot fi obținuți din toate perechile diferite de numere din șir și să se afișeze aceștia.  = Date de intrare = Fișierul de intrare <code>factorulx.in</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n<...
New page


= Cerința =

Numim factorul-x a <code>2</code> numere produsul tuturor factorilor primi comuni și diferiți ai celor <code>2</code> numere.



Se dau <code>n</code> numere naturale distincte. Se cere să se afle câți factori-x diferiți pot fi obținuți din toate perechile diferite de numere din șir și să se afișeze aceștia.



= Date de intrare =

Fișierul de intrare <code>factorulx.in</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale distincte separate prin spații.



= Date de ieșire =

Fișierul de ieșire <code>factorulx.out</code> va conține pe prima linie numărul de factori-x diferiți care pot fi obținuți din toate perechile diferite de numere din șir, iar pe a <code>2</code>-a linie toți aceștia, afișați în ordine crescătoare și separați prin câte un spațiu.



= Restricții și precizări =



* <code>1 ≤ n ≤ 1000</code>

* numerele de pe a doua linie a fișierului de intrare vor fi distincte și mai mici decât <code>2.000.000.000</code>

* dacă <code>2</code> numere nu au niciun factor prim comun, atunci, prin convenție se alege ca factorul-x al celor <code>2</code> numere să fie <code>1</code>

* punctajul pe test va fi acordat doar dacă ambele numere afișate sunt corecte.



= Exemplu: =

<code>factorulx.in</code>

 9

 2 4 6 7 9 15 18 20 21

<code>factorulx.out</code>

 6

 1 2 3 5 6 7



= Explicatie: =

Factorul-x pentru <code>15</code> și <code>18</code> este <code>3</code>(<code>3</code> este singurul lor factor prim comun), pentru <code>7</code> și <code>21</code> este <code>7</code> (la fel ca în cazul anterior), pentru <code>6</code> și <code>18</code> este <code>6</code>(<code>2 * 3</code>), pentru <code>2</code> și <code>7</code> este <code>1</code> etc.



== Încărcare soluție ==

<syntaxhighlight line="1">

import math



f = open("factorulx.in", "r")

g = open("factorulx.out", "w")



def factorx(n):

    P = 1

    if n % 2 == 0:

        P *= 2

        while n % 2 == 0:

            n >>= 1

    for i in range(3, int(math.sqrt(n)) + 1, 2):

        if n % i == 0:

            P *= i

            while n % i == 0:

                n = n // i

    if n > 2:

        P *= n

    return P



n = int(f.readline())

v = [0] * 1024

fact = [0] * 524288



i = 0

j = 0

m = 0

k = 0

P = 0



for i in range(1, n + 1):

    v[i] = int(f.readline())



for i in range(1, n):

    for j in range(i + 1, n + 1):

        m = math.gcd(v[i], v[j])

        P = factorx(m)

        if P not in fact[1:k + 1]:

            k += 1

            fact[k] = P

            fact[1:k + 1].sort()



g.write(str(k) + '\n')

fact[1:k + 1].sort()

for i in range(1, k + 1):

    g.write(str(fact[i]) + " ")



f.close()

g.close()



</syntaxhighlight>

3486 - Factorul IX - Revision history