Запишите умножение a × b = c и рассмотрите все цифры чисел a, b и c вместе. Равенство называется n-пандигитальным, если это цифры 1, 2, ..., n, каждая ровно по одному разу (нулей нет). Для n = 4 подходит 3 × 4 = 12. Найдите все произведения c, которые встречаются хотя бы в одном n-пандигитальном равенстве.
Реализуйте pandigital_products(n).
Входные данные
n: наибольшая используемая цифра.
Выходные данные
Верните сумму различных произведений c. Произведение, которое получается из нескольких равенств, учитывается один раз. Если таких произведений нет, верните 0.
Ограничения
1 ≤ n ≤ 9
Примеры
Ввод:
n = 4
Ожидаемый вывод:
expected = 12
Ввод:
long long n = 4;
Ожидаемый вывод:
long long expected = 12;
Ввод:
long n = 4;
Ожидаемый вывод:
long expected = 12;
Пояснение
3 × 4 = 12 использует 1, 2, 3, 4 по одному разу, и это единственное такое равенство, поэтому ответ 12.
Ввод:
n = 3
Ожидаемый вывод:
expected = 0
Ввод:
long long n = 3;
Ожидаемый вывод:
long long expected = 0;
Ввод:
long n = 3;
Ожидаемый вывод:
long expected = 0;
Пояснение
С цифрами 1, 2, 3 возможны только разбиения вроде 1 × 2 = 3, а это неверно, поэтому ответ 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Каждое n-пандигитальное равенство - это перестановка цифр от 1 до n, разрезанная на три части.
Подсказка 2
Перебирайте все пары точек разреза и проверяйте, равно ли произведение первых двух частей третьей.
Подсказка 3
Храните произведения в множестве, чтобы каждое учитывалось один раз.
Ожидаемая сложность
время O(n! × n²), доп. память O(number of products)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.