Описание задачи
Для каждого положительного целого числа nсуществует число, имеющее форму, 111...10...000которая делится на nто есть десятичное число, которое начинается со всех 1и заканчивается всеми 0. Это очень легко доказать: если мы возьмем набор n+1различных чисел в виде 111...111(все 1), то по крайней мере два из них дадут один и тот же остаток после деления на n(согласно принципу голубя). Разница между этими двумя числами будет кратна nи будет иметь желаемую форму. Ваша цель - написать программу, которая найдет этот номер.
Описание ввода
Целое положительное число.
Описание вывода
Число pв форме 111...10...000, такое что p ≡ 0 (mod n). Если вы найдете более одного - отобразите любой из них (необязательно самый маленький).
Заметки
Ваша программа должна дать ответ в разумные сроки. Что означает, что грубое принуждение не разрешено:
p = 0
while (p != 11..10.00 and p % n != 0)
p++
И это не так:
do
p = random_int()
while (p != 11..10.00 and p % n != 0)
Итерация по номерам в форме 11..10..00разрешена.
Ваша программа не должна обрабатывать произвольно большие входные данные - верхняя граница равна верхней границе вашего языка.
Пример выходов
2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
источник
1и хотя бы одно0, иначе0это решение для любого ввода. (Было бы хорошо, чтобы уточнить это, хотя.)1должен работать.Ответы:
Mathematica, 29 байт
Код Мартина Бюттнера .
На входе
nэто выводит число с9*ϕ(n)единицами, за которыми следуютnнули, гдеϕнаходится функция Эйлера . С помощью функцииphiэто можно выразить в Python какБыло бы достаточно использовать факториал
n!вместоϕ(n), но для печати, что многие из них не имеют разумного времени выполнения.Утверждение:
9*ϕ(n)единицы, за которыми следуютnнули, кратныn.Доказательство: Во- первых, давайте докажем это для случая,
nне является кратным2,3или5. Мы покажем, что число, состоящее изϕ(n)единиц, кратно `n.Количество из
kних равно(10^k-1)/9. Такnкак не является кратным3, это кратноnстолько, сколько10^k-1является факторомn, или эквивалентно, если10^k = 1 (mod n). Обратите внимание, что эта формулировка делает очевидным, что еслиkработает для числа единиц, то так же, как любой кратныйk.Таким образом, мы ищем
kбыть кратна порядка изkв мультипликативной группе по модулю п . По теореме Лагранжа , любой такой порядок является делителем размера группы. Поскольку элементами группы являются числа от,1кnкоторым относительно простые числаn, ее размер является функцией Эйлераϕ(n). Итак, мы показали10^ϕ(n) = 1 (mod n), что число сделанных изϕ(n)них кратно `n.Теперь давайте рассмотрим потенциальные факторы
3вn. Мы знаем, что10^ϕ(n)-1это кратноn, но(10^ϕ(n)-1)/9не может быть. Но,(10^(9*ϕ(n))-1)/9является кратным,9потому что он состоит из9*ϕ(n)единиц, поэтому сумма его цифр кратна9. И мы отметили, что умножение показателя степениkна константу сохраняет делимость.Теперь, если
nесть факторы2's' и5's', нам нужно добавить нули в конец вывода. Это более чем достаточно, чтобы использоватьnнули (на самом делеlog_2(n)будет делать). Таким образом, если наш входnразделен наn = 2^a * 5^b * m, достаточно иметь9*ϕ(m)кратные единицыn, умноженные10^nна кратные2^a * 5^b. И, такnкак кратноm, достаточно использовать9*ϕ(n)их. Таким образом, это работает, чтобы иметь9*ϕ(n)единицы послеnнулей.источник
EulerPhiфункцию. В реальной реализации нет ничего потрясающего, так что я бы полностью рассмотрел эту работу.Python 2, 44 байта
Когда
jэто степень 10, такая как 1000, деление по полуj/9дает число, состоящее из 1, как 111. Таким образом,j/9*jдает 1, за которым следует такое же число 0, как 111000.Функция рекурсивно проверяет числа этой формы, пробуя все более высокие степени 10, пока мы не найдем число, кратное желаемому числу.
источник
Pyth, 11 байт
Тестирование
По сути, он просто ставит 1 впереди и 0 снова и снова, пока число не делится на вход.
Объяснение:
источник
Haskell, 51 байт
Используя подход xnor. Ними спасла байт!
источник
CJam,
282519 байтовСохранено 6 байтов с наблюдением xnor, что нам нужно только взглянуть на числа в форме .
1n0nПроверьте это здесь.
объяснение
источник
Mathematica,
14055 байтМногие байты удалены благодаря трюку xnor 1 ^ n0 ^ n.
Минимальное значение,
140156 байт. Это дает наименьшее возможное решение.Он вычисляет, сколько нулей требуется, затем проверяет все возможные значения,
1пока он не заработает. Он может выводить число без 0, но это можно исправить, добавив<>"0"право перед финалом&.источник
Haskell, 37 байт
Это использует тот факт, что он работает, чтобы иметь
9*phi(n)те, гдеphiесть функция Эйлера. Здесь он реализован с использованиемgcdи фильтрации, производя одну цифру для каждогоiотносительно простого значения , которое находится в диапазоне1и9*n. Также достаточно использовать это множество нулей.источник
JavaScript (ES6), 65 байт
Редактирование 2 байт сохраненного ТНХ @Neil
Это работает в пределах числового типа javascript, с 17 значащими цифрами. (Так довольно ограничено)
Меньше гольфа
источник
for(m=n;?for(m=n;!m[16];)if(!((m+=0)%a)).Perl 5, 26 байт
включает байт для
-n(-M5.01бесплатно)источник
Sage, 33 байта
Это использует метод xnor, чтобы произвести вывод.
Попробуйте онлайн
источник
до н.э., 58 байт
Пример результатов
источник
постоянный ток, 27 байт
Это определяет функцию,
fкоторая ожидает свой аргумент в переменнойn. Чтобы использовать его в качестве программы,?sn lfx pдля чтения из стандартного ввода, вызова функции и вывода результата в стандартный вывод. Переменнаяmи вершина стека должны быть сброшены до 10 (путем повторенияOdsm), прежде чем ихfможно будет использовать повторно.Полученные результаты:
источник