Pythonist

Условие:

Каждое n-значное число, содержащее каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым. К примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.

Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения, является пан-цифровым, т.е. содержит цифры от 1 до 9.

Найдите сумму всех пан-цифровых произведений, для которых равенство «множимое × множитель = произведение» можно записать цифрами от 1 до 9, используя каждую цифру только один раз.

ПОДСКАЗКА: Некоторые произведения можно получить несколькими способами, поэтому убедитесь, что включили их в сумму лишь единожды.

Решение:

Для решения этой задачи нам понадобятся 2 вспомогательные функции:

1-я функция sqrt() — принимает на вход integer и возвращает floor(sqrt(x)), где floor(x) — числовая функция, которая возвращает наибольшее целое число, не больше чем x.

2-я — has_pandigital_product(n) — проверяет, есть ли пан-цифровое значение.

# Given integer x, this returns the integer floor(sqrt(x)).
def sqrt(x):
 assert x >= 0
 i = 1
 while i * i <= x:
  i *= 2
 y = 0
 while i > 0:
  if (y + i)**2 <= x:
   y += i
  i //= 2
 return y


def has_pandigital_product(n):
 for i in range(1, sqrt(n) + 1):
  if n % i == 0:
   temp = str(n) + str(i) + str(n // i)
   if "".join(sorted(temp)) == "123456789":
    return True
 return False


def compute():
 ans = sum(i for i in range(1, 10000) if has_pandigital_product(i))
 return str(ans)


if __name__ == "__main__":
 print(compute())