Es un número cuyo mcd de (suma de la potencia cuartica de sus dígitos, el producto de sus dígitos) es mayor que 1. ej. 123 es un número especial porque mcf de (1+16+81, 6) es mayor que 1.
Tengo que encontrar el conteo de todos estos números que están debajo de la entrada n. p.ej. para n=120 hay 57 números especiales entre (1 y 120)
He hecho un código, pero es muy lento, ¿puede decirme que lo haga de una manera buena y rápida? ¿Hay alguna manera de hacerlo usando algunas matemáticas?
import math,numpy t = int(input()) ans = [] for i in range(0,t): ans.append(0) n = int(input()) for j in range(1, n+1): res = math.gcd(sum([pow(int(k),4) for k in str(j)]),numpy.prod([int(k) for k in str(j)])) if res>1: ans[i] = ans[i] + 1 for i in range(0,t): print(ans[i])La observación crítica es que las representaciones decimales de números especiales constituyen un lenguaje regular. A continuación se muestra un reconocedor de estado finito en Python. Esencialmente rastreamos los factores primos del producto (mcd > 1 es equivalente a tener un factor primo en común) y el residuo de la suma de potencias mod 2×3×5×7, así como un poco de estado para manejar casos extremos que involucran ceros.
A partir de ahí, podemos construir un autómata explícito y luego contar el número de cadenas de aceptación cuyo valor es menor que n usando programación dinámica.
def is_special(digits): greater_than_zero = False greater_than_one = False prod_zero = False prod_two = False mod_two = 0 prod_three = False mod_three = 0 prod_five = False mod_five = 0 prod_seven = False mod_seven = 0 for d in digits: if d > 1: greater_than_one = True elif d == 1: if greater_than_zero: greater_than_one = True else: greater_than_zero = True if d == 0: prod_zero = True if d % 2 == 0: prod_two = True mod_two = (mod_two + d ** 4) % 2 if d % 3 == 0: prod_three = True mod_three = (mod_three + d ** 4) % 3 if d % 5 == 0: prod_five = True mod_five = (mod_five + d ** 4) % 5 if d % 7 == 0: prod_seven = True mod_seven = (mod_seven + d ** 4) % 7 return ( greater_than_one if prod_zero else ( (prod_two and mod_two == 0) or (prod_three and mod_three == 0) or (prod_five and mod_five == 0) or (prod_seven and mod_seven == 0) ) ) # Test case import functools import math import operator def digits_of(n): return [int(digit) for digit in str(n)] def is_special_reference(digits): power_sum = sum(digit ** 4 for digit in digits) product = functools.reduce(operator.mul, digits, 1) return math.gcd(power_sum, product) > 1 def test(): for n in range(10000): digits = digits_of(n) assert is_special(digits) == is_special_reference(digits), str(n) if __name__ == "__main__": test()