Danciu: Pagină nouă: Fie `D`, `K` și `P` trei numere naturale. == Cerința == Să se determine numărul de numere naturale, notat cu `T`, având următoarele proprietăți: * au exact `D` divizori; * descompunerea în factori primi a acestor numere conține exact `K` numere prime; * toți factorii primi din descompunerea numerelor sunt mici sau egali cu `P`. == Date de intrare == Fișierul de intrare `divizori.i...`


2024-06-04T09:04:49Z
Pagină nouă: Fie <code>D</code>, <code>K</code> și <code>P</code> trei numere naturale.  == Cerința == Să se determine numărul de numere naturale, notat cu <code>T</code>, având următoarele proprietăți:  * au exact <code>D</code> divizori; * descompunerea în factori primi a acestor numere conține exact <code>K</code> numere prime; * toți factorii primi din descompunerea numerelor sunt mici sau egali cu <code>P</code>.  == Date de intrare == Fișierul de intrare <code>divizori.i...
New page
Fie <code>D</code>, <code>K</code> și <code>P</code> trei numere naturale.



== Cerința ==

Să se determine numărul de numere naturale, notat cu <code>T</code>, având următoarele proprietăți:



* au exact <code>D</code> divizori;

* descompunerea în factori primi a acestor numere conține exact <code>K</code> numere prime;

* toți factorii primi din descompunerea numerelor sunt mici sau egali cu <code>P</code>.



== Date de intrare ==

Fișierul de intrare <code>divizori.in</code> conține pe primul rând numerele <code>D</code>, <code>K</code> și <code>P</code> cu semnificația de mai sus, despărțite prin câte un spațiu.



== Date de iesire ==

Fișierul de ieșire <code>divizori.out</code> va conține pe primul rând restul împărțirii numărului <code>T</code> la <code>3000017</code>



== Restricții și precizări ==



* <code>2 ≤ D ≤ 1014</code>

* <code>1 ≤ K ≤ 100</code>

* <code>2 ≤ P ≤ 1.000.000</code>



= Exemplul 1: =

<code>divizori.in</code>

 6 2 5

<code>divizori.out</code>

 6



=== Explicație ===

<code>D = 6</code>, <code>K = 2</code>, <code>P = 5</code>. Sunt <code>T = 6</code> numere cu exact <code>6</code> divizori ce conțin în descompunerea în factori primi exact două numere prime mai mici sau egale decât <code>5</code>: <code>2132</code>, <code>2152</code>, <code>2231</code>, <code>2251</code>, <code>3152</code>, <code>3251</code>.



= Exemplul 2: =

<code>divizori.in</code>

 18 3 10

<code>divizori.out</code>

 12



= Exemplul 3: =

<code>divizori.in</code>

 10 8 17

<code>divizori.out</code>

 0



=== Explicație ===

<code>D = 10</code>, <code>K = 8</code>, <code>P = 17</code>. Nu există numere cu exact <code>10</code> divizori ce conțin în descompunerea în factori primi exact <code>8</code> numere prime mai mici sau egale cu <code>17</code> deoarece sunt doar <code>7</code> numere prime mai mici sau egale decât <code>17</code>.



== Rezolvare ==

<syntaxhighlight lang="python3">

MOD = 3000017  



def count_numbers_with_properties(d, k, p):

    dp = [[0 for _ in range(k + 1)] for _ in range(d + 1)]



    for i in range(k + 1):

        for j in range(1, d + 1):

            if j == 1:

                dp[j][i] = 1



    for i in range(2, d + 1):

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

            dp[i][j] = 0



            for num_divisors in range(1, i):

                if j >= 2:

                    dp[i][j] += dp[num_divisors][j - 1] * dp[i - num_divisors][j]

                else:

                    # If j = 1, all prime factors must be distinct

                    if num_divisors == 1:

                        dp[i][j] += dp[num_divisors][j]



    total_numbers = 0

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

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

            # Limit prime factors to 'p'

            if max_prime_factor_up_to_p(dp[i][j], p) == dp[i][j]:

                total_numbers += dp[i][j]



    return total_numbers % MOD



def max_prime_factor_up_to_p(n, p):

    max_prime_factor = 1

    while n % 2 == 0:

        n //= 2

        max_prime_factor = 2



    for i in range(3, int(p ** 0.5) + 1, 2):

        while n % i == 0:

            n //= i

            max_prime_factor = i



    if n > 1:

        max_prime_factor = n



    return max_prime_factor



def main():

    with open("divizori.in", "r") as input_file:

        d, k, p = map(int, input_file.readline().split())



    number_count = count_numbers_with_properties(d, k, p)



    with open("divizori.out", "w") as output_file:

        output_file.write(str(number_count))



if __name__ == "__main__":

    main()



</syntaxhighlight>
3090 - divizori5 - Revision history
