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

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