3090 - divizori5

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.in conține pe primul rând numerele D, K și P cu semnificația de mai sus, despărțite prin câte un spațiu.

Date de iesire

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

Restricții și precizări

• 2 ≤ D ≤ 1014
• 1 ≤ K ≤ 100
• 2 ≤ P ≤ 1.000.000

Exemplul 1:

divizori.in

6 2 5

divizori.out

6

Explicație

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

Exemplul 2:

divizori.in

18 3 10

divizori.out

12

Exemplul 3:

divizori.in

10 8 17

divizori.out

0

Explicație

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

Rezolvare

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()