Editing 3090 - divizori5

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>