Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.

Формат входных данных:
Натуральное число n (1≤n≤999).
формат результата:
Если задачу выполнить нельзя то вывести «Impossible». Если задачу выполнить можно — вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.
Примеры

Входные данные в файле input.txt	Результат работы в файле output.txt
37	1 3
25	Impossible

Вопрос:
1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?
2) если результата нет, то как выяснить не применяя перебор: возможно есть какая-либо теорема, математическая закономерность? (или все-таки применять перебор вариантов, тогда когда его остановить?)
3) "количество цифр которые может отображать калькулятор считать неограниченным" — это означает, что применяется длинная арифметика?

Для чисел, что не делятся на 2 и 5, далеко перебирать не придётся, чтобы получить число из девяток, потому что есть теорема.

Здравствуйте, olimp_20, Вы писали:

_>Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.

_>Формат входных данных:
_>Натуральное число n (1≤n≤999).
_>формат результата:
_>Если задачу выполнить нельзя то вывести «Impossible». Если задачу выполнить можно — вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.
_>Примеры

_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>
_>

Входные данные в файле input.txt	Результат работы в файле output.txt
37	1 3
25	Impossible

_>Вопрос:
_>1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?
_>2) если результата нет, то как выяснить не применяя перебор: возможно есть какая-либо теорема, математическая закономерность? (или все-таки применять перебор вариантов, тогда когда его остановить?)
_>3) "количество цифр которые может отображать калькулятор считать неограниченным" — это означает, что применяется длинная арифметика?

Думаю, тут где-то малая теорема Ферма рядом пробегала... Например, число из одних девяток точно можно получить, если n взаимно просто с 10, т.к. 10^n-1 = 1 (mod n). Про другие надо подумать.

Здравствуйте, olimp_20, Вы писали:

Переберем все цифры от 1 до 9.
Обозначим текущую проверяемую цифру как d.
Тогда нам надо найти некоторое число вида Xm = d*11...1(m единиц) или понять, что такого числа не существует.
Последовательность Ym = Xm % n = (d*11...1(m единиц)) % n — циклична.
Поэтому просто идем начиная с ее первого члена пока не наткнемся на Ym = 0.
Если наткнулись, то восстановить число — не проблема: d*11...1(m единиц).
Если очередной элемент последовательности != 0, то запоминаем его и идем дальше.
Если все возможные значения элементов Ym проверены, а число не нашлось, то для данной цифры искомого числа не существует.
Поскольку последовательность состоит из остатков от деления на n, то для каждой цифры потребуется не более n проверок.

Здравствуйте, StatujaLeha, Вы писали:

SL>Здравствуйте, olimp_20, Вы писали:

SL>Переберем все цифры от 1 до 9.
SL>Обозначим текущую проверяемую цифру как d.
SL>Тогда нам надо найти некоторое число вида Xm = d*11...1(m единиц) или понять, что такого числа не существует.
SL>Последовательность Ym = Xm % n = (d*11...1(m единиц)) % n — циклична.
SL>Поэтому просто идем начиная с ее первого члена пока не наткнемся на Ym = 0.
SL>Если наткнулись, то восстановить число — не проблема: d*11...1(m единиц).
Число не так восстановил: d*11...1(m единиц)/n

SL>Если очередной элемент последовательности != 0, то запоминаем его и идем дальше.
SL>Если все возможные значения элементов Ym проверены, а число не нашлось, то для данной цифры искомого числа не существует.
SL>Поскольку последовательность состоит из остатков от деления на n, то для каждой цифры потребуется не более n проверок.

Здравствуйте, olimp_20, Вы писали:


_>Вопрос:
_>1) если можно найти ответ, то чем ограничить перебор чисел из одинаковых цифр?

Можно ограничить:
10^m

(где m — заданное число, меньшее 999).

Пусть G(k) = 111...1 (k единиц).
G(k) = (10^k-1)/9,
G(k+1) = G(k)*10+1

Рассмотрим последовательность S(k) = G(k) % m.

S(k+1) = (S(k)*10 +1) % m

Очевидно, S(k)<m для любого k.
Следовательно длинна периода S(k), также должна быть не больше m,
(поскольку все числа S(k) в пределах одного периода должны быть уникальны).

P.S.
Для чисел состоящих из других цифр — действует аналогичное ограничение.

Здравствуйте, olimp_20, Вы писали:

_>Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.

Читать про делители репьюнитов
Вот здесь интересно Удивительные приключения периодических дробей

Или так:

Максимальное количество цифр в искомом числе равное N.
Нужно проверить все числа у которых все цифры одинаковые и число цифр не более N. Таких чисел всего порядка 10*N
Для каждого числа (в порядке возрастания) проверяем делится ли оно на N. Первое найденное число — ответ.

Т.к. числа большие (длинная арифметика), то операции с каждым числом занимают O(количество цифр), в нашем случае O(N).
Итого сложность алгоритма O(N^2), где N — заданное число

Здравствуйте, Буравчик, Вы писали:

Б>Т.к. числа большие (длинная арифметика), то операции с каждым числом занимают O(количество цифр), в нашем случае O(N).

Нет там длинной арифметики, при дописывании цифры надо произвести простые операции с предыдущим остатком, за константу. Итого полное время O(N).