#1766

Интересное число

Темы: [Динамическое программирование на таблицах] [Остатки]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2004, Задача F ]

Задано число N. Требуется найти наименьшее число с суммой цифрой, равной N, которое делится на N.

Для заданного числа \(n\) найдите наименьшее положительное целое число с суммой цифр \(n\), которое делится на \(n\).

Входные данные

Во входном файле содержатся целое число \(n\) (1 ≤ \(n\) ≤ 1000).

Выходные данные

Выходной файл должен содержать искомое число. Ведущие нули выводить не разрешается.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

#1783

Игра с графом

Темы: ["Длинная" арифметика]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2006, Задача D ]

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены \(n\) кружочков, помеченных числами от 1 до \(n\). Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек \(b\) разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Проигрывает тот, кто не может сделать ход.

Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на доске.

Входные данные

Входной файл содержит одно число \(n\) (1 ≤ \(n\) ≤ 100).

Выходные данные

Выведите в выходной файл число возможных позиций без ведущих нулей.

Пояснение к примеру

Примеры

Входные данные

Выходные данные

#1787

Число

Темы: [Простые числа и разложение на множители]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2006, Задача H ]

По заданным числам \(a\), \(b\), \(c\) и \(d\), найдите наименьшее натуральное число \(n\), большее \(ac\), которое нельзя представить в виде произведения двух натуральных чисел \(u\) и \(v\), таких что \(a\) ≤ \(u\) ≤ \(b\) и \(c\) ≤ \(v\) ≤ \(d\).

Входные данные

Входной файл содержит одну строку, состоящую из натуральных чисел \(a\), \(b\), \(c\), \(d\) (1 ≤ \(a\) ≤ \(b\) ≤ \(10^6\), 1 ≤ \(c\) ≤ \(d\) ≤ \(10^6\)).

Выходные данные

Выведите в выходной файл искомое число \(n\).

Примеры

Входные данные

1 2 1 2

Выходные данные

Входные данные

1 2 3 5

Выходные данные

#1834

Парные числа

Темы: [Простые числа и разложение на множители]

Назовём парой простого числа p такое простое число \(x\), что |\(p\) − \(x\)| = 2 . На отрезке [\(a\), \(b\)] найдите количество простых чисел, имеющих пару.

Входные данные

В единственной строке входного файла содержатся два натуральных числа \(a\) и \(b\) (2 \(\le\) \(a\) \(\le\) \(b\) \(\le\) 36 * \(10^6\)).

Выходные данные

Выведите единственное натуральное число — количество простых чисел, принадлежащих отрезку [\(a\), \(b\)], имеющих пару.

Примеры

Входные данные

2 10

Выходные данные

#1838

Отрезок

Темы: [НОД и алгоритм Евклида]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2009, Задача D ]

На клетчатой бумаге Петя нарисовал отрезок из точки с координатами (\(a\),\(b\)) в точку с координатами (\(c\),\(d\)). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через ее внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку).

Входные данные

Вводятся целые числа \(a\), \(b\), \(c\), \(d\). Числа по модулю не превышают \(10^9\).

Выходные данные

Выведите одно число — количество клеток, через которые проходит отрезок.

Примеры

Входные данные

0 0 6 4

Выходные данные

Входные данные

3 3 -3 3

Выходные данные