Информатика

Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A.
 

Входные данные 
На вход подается единственное число A (\(1 <= A <= 10^9\)).

 

Выходные данные
Необходимо вывести единственное число N.

 

Примеры

№	Входные данные	Выходные данные
1	8	4
2	13	13

данное натуральное число a кратно числу b, но не кратно числу с

С клавиатуры вводится три числа, каждое в отдельной строке: в первой строке вводится число a, во второй - b, в третьей - с

сумма двух натуральных чисел кратна 2

Формат входных данных
Программа получает на вход два натуральных числа: каждое число записано в отдельной строке (каждое число не больше 100)

Формат выходных данных
Выведите 1 или 0.

данное четырехзначное число читается одинаково слева направо и справа налево

ПРИМЕР:
вход: 1221
вывод: 1

ПРИМЕР:
вход: 2727
вывод: 0

целое число N является четным двузначным числом

Формат входных данных
Программа получает на вход одно натуральное число (число не превышает 1000)

Формат выходных данных
Выведите 1 или 0.

 

Примеры

№	Входные данные	Выходные данные
1	12	1
2	27	0

квадрат заданного двухзначного числа равен кубу суммы цифр этого числа

ПРИМЕР:
вход: 12
вывод: 0

ПРИМЕР:
вход: 27
вывод: 1

сумма цифр данного трехзначного числа является четным числом

ПРИМЕР:
вход: 123
вывод: 1

ПРИМЕР:
вход: 122
вывод: 0

сумма первых двух цифр заданного четырехзначного числа равна сумме двух его последних цифр

Формат входных данных
Программа получает на вход одно натуральное четырехзначное число

Формат выходных данных
Выведите 1 или 0.

 

Примеры

№	Входные данные	Выходные данные
1	1234	0
2	1221	1

Президент Берляндии обратился к вам за помощью! В его стране есть n городов. Между некоторыми парами городов есть двусторонние дороги. Совсем скоро откроется туристический сезон, но дороги Берляндии совсем не готовы к такому испытанию.

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

Найти множество дорог, которые нужно отремонтировать, вам поможет ваш друг. Вам только требуется подсчитать минимальную стоимость ремонта.

Гарантируется, что всегда найдется необходимое множество дорог.

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

В первой строке задано два целых числа - n и m (2 <= n <= 300000, n - 1  <= m <= 300000).

В следующих m строках содержатся три числа - u, v и w (1 <= u, v <= n, 0 <= w <= 10⁹) - дорога между городами u и v, стоимость ремонта которой w.

Ввод	Вывод
3 3 1 2 1 1 2 3 1 3 4	5
2 4 1 2 0 1 2 1 1 2 2 1 2 3	0

(с) Ибрахим Ахмад, 2018

Есть n вершин неориентированного графа, в нем же нет ребер. В граф постепенно добавляются m ребер. 

После каждого добавления ребра требуется узнать количество компонент связности.

В графе могут быть петли и кратные ребра.

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

В первой строке два числа  - n и m (1 <= n <= 300000, 0  <= m <= 500000) - количество вершин графа и количество добавляемых ребер. 

В следующих m строках по два числа u, v (1 <= u, v <= n) - они значат, что в граф добавили ребро (u, v).

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

После каждого добавления ребра выведите количество компонент связности графа.

Ввод	Вывод
3 2 1 2 2 3	2 1
3 6 1 1 2 2 3 3 1 1 2 2 1 2	3 3 3 3 3 2

(с) Ибрахим Ахмад, 2018

Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.

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

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента C_i (1 ≤ C_i ≤ 3000), его рейтинг R_i (1 ≤ R_i ≤ 3000) и его тип t_i (1 ≤ t_i ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод	Вывод
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16	18 2 5

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 10⁹, разделенных пробелами.

Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Ввод	Вывод
6 1 2 701000 299000 1000 999000	2 3
3 1 2 3	-1

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.

Напишите программу, которая поможет Стелле провести классификацию снежинок.

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a₁ a₂ a₃ a₄ a₅ a₆ от 1 до 10⁹, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.

Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод	Вывод
5 1 2 3 4 5 6 3 4 5 6 1 2 3 2 1 4 5 6 6 5 4 3 2 1 2 3 6 5 4 1	2

Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.

 

Входные данные 
Натуральные числа и не превышают по модулю 10000.

Выходные данные 
Выведите ответ на задачу.