Арифметические алгоритмы (Теория чисел)

114 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Премия#30774
Несмотря на кризис, компания Soft-Soft работает успешно. Директор компании принял решение выплатить сотрудникам премии. На следующий день был обнародован список счастливчиков. Чтобы не разглашать размер выплат, в списке напротив фамилий красовались странные цифры и даже буквы. Сотрудники быстро догадались, что размер премий записан в различных системах счисления. Но где и какая система счисления используется, сообразила только секретарша Танечка, которая вспомнила, что директор просил ее принести информацию о возрасте сотрудников. Она поняла, что директор отбрасывал десятки из числа, указывающего возраст, а к оставшимся единицам добавлял число 2. Полученное значение служило основанием для представления начисленной премии.
 
Помогите любопытной Танечке узнать размер премий в десятичной системе счисления. Известно, что размер премий не превышает 100000 рублей в десятичной системе счисления.
 
Входные данные
В первой строке  записаны два целых числа N и K – возраст и размер премии, разделенные пробелом. Возраст не превышает 100, размер премии указан в некоторой системе счисления (запись числа не содержит незначащих нулей, использует арабские цифры и заглавные английские буквы).
 
Выходные данные
Выведите одно число – размер премии в десятичной системе счисления.
 

 

Примеры
№ Входные данные Выходные данные
1 28 2800 2800
2 30 101 5
Разные системы счисления
✓ 142✗ 341600лёгкаяВойти и решать
Простые числа - 2#30773
Из заданного набора чисел выберите одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).
 
Входные данные 
Первая строка  содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.
 
Выходные данные 
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.
 
Примеры
№ Входные данные Выходные данные
1
10
3 5 7 9 11 13 15 17 19 21
 15
2
11
2 4 6 8 10 13 39 105 200 201 143
 105
Простые числа и разложение на множители
✓ 424✗ 1 136600лёгкаяВойти и решать
Разложение числа на 5 и 3#30771
На сколько пятерок и троек можно разложить число, чтобы количество разложений было минимально.

Входные данные
На вход подается одно натуральное число N (\(7 < N < 1000\)).

Выходные данные
Выведите два целых числа через пробел: число пятерок и число троек.
 

 

Примеры
№ Входные данные Выходные данные
1 8 1 1
2 11 1 2
3 15  3 0
Остатки
✓ 134✗ 141500лёгкаяВойти и решать
Единичный НОД#30770
Заданы два натуральных числа в десятичной системе счисления, состоящие из единиц. В первом числе ровно N единиц, а во втором их ровно M. Требуется найти НОД этих чисел. 
 
Входные данные
В единственной строке  записаны два целых числа N и M (\(1 <= N,\ M <= 2000\)).
 
Выходные данные
Выведите ответ без ведущих нулей.
 

 

Примеры
№ Входные данные Выходные данные
1 1 1 1
2 1 2 1
НОД и алгоритм Евклида
✓ 370✗ 477500лёгкаяВойти и решать
Разложение на простые - 1#29549
Требуется разложить целое число N на простые множители, представив его в виде произведения простых множителей и вывести результат в порядке возрастания.
 
Входные данные  
На вход падается число N (\(2 <= N <= 10^9\)).
 
Выходные данные 
Выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».
 
Примеры
№ Входные данные Выходные данные
1 5 5
2 30 2*3*5
Простые числа и разложение на множители
✓ 954✗ 1 847400лёгкаяВойти и решать
Разложение на простые - 2#29548
Требуется разложить целое число N на простые множители, представив его в виде произведения степеней простых множителей и вывести результат в порядке возрастания.
 
Входные данные 
На входе дано число N (\(2 <= N <= 10^9\)).
 
Выходные данные 
Вывести разложение N на простые множители.
 
Примеры
№ Входные данные Выходные данные
1 2 2
2 1008 2^4*3^2*7
Простые числа и разложение на множители
✓ 627✗ 1 580500лёгкаяВойти и решать
Сокращение дроби#29423
Дана дробь \(a \over b\). Требуется ее сократить, то есть записать это же число в виде \(c \over d\), где c — целое число, d - натуральное число и d минимальное возможное.
 
Входные данные 
Вводятся два целых числа a и b (\(-100<=a<=100,\ 0<b<=100\)).

Выходные данные 
Выведите два числа c и d.
 
Примеры
№ Входные данные Выходные данные
1 3 6  1 2
2 -2 5 -2 5
НОД и алгоритм Евклида
✓ 1 331✗ 3 701400лёгкаяВойти и решать
27031#27031
Сколько существует таких натуральных чисел в диапозоне от a до b, что их запись в шестнадцатеричной системе счисления будет иметь ровно две значащих цифры, а в восьмеричной системе счисления – ровно три значащих цифры?
Задача на реализациюРазные системы счисления
✓ 99✗ 153500лёгкаяВойти и решать
Алгоритм#27018
Реализуйте алгоритм, представленный блок-схемой, на одном из языков программирования.
 
В первой строке ввода содержится одно целое число N (2 ≤ N ≤ 109).
Каждое число, которое выводится в алгоритме, вывести на отдельной строке.



Ввод Вывод
12 2
2
3

Задачи на моделированиеПростые числа и разложение на множители
✓ 66✗ 75500лёгкаяВойти и решать
НОД и НОК#24905

Дано число n – количество чисел. В следующей строке дано n чисел, каждое не больше 1000.
Вам необходимо вывести количество таких пар чисел (a, b), что НОК (a, b) = НОД (a, b).

НОК (a, b) - наименьшее общее кратное этих двух чисел, то есть наименьшее число, которое делится сразу на оба числа. \( НОК (20, 30) = 60\).
НОД (a, b) – наибольший общий делитель этих двух чисел, то есть наибольшее число, на которое делятся оба числа. \(НОД (20, 30) = 10\).
Напишите эффективную по памяти и времени программу.

Входные данные
В первой строке вводится натуральное число n – количество данных вам чисел.
Во второй строке вводятся сами числа, каждое из них целое и принадлежит отрезку [0; 1000].
 
Выходные данные
Выведите одно целое число – количество пар чисел (a, b), таких, что НОК(a,b) = НОД(a,b).
 

 

Примеры
№ Входные данные Выходные данные
1 3
3 3 3		 3

 

НОД и алгоритм Евклида
✓ 636✗ 2 555600лёгкаяВойти и решать
Интересные числа (С', C)#23334
Маленький Вася очень любит числа, а особенно сильно он любит интересные числа. Вася считает число x интересным,  если сумма квадратов его цифр делится на число 7. Например, число 123 -
интересное, потому что 12 + 22 + 32 = 14 делится на 7, а число 16 - нет, потому что 12 + 62 = 37 не делится на 7. Однажды Вася увидел на доске число x, он сразу же захотел узнать величину минимального интересного числа, которое строго больше чем x.  Так как Вася еще слишком юн, он обратился к вам за помощью в решение этой задачи.
 
Формат входных данных
Во входном файле содержится единственное целое число x - число, написанное на доске 0<= x <= 105
 
Формат выходных данных
В единственную строку выходного файла выведите минимальное интересное число, которое строго больше чем x.
Ввод Вывод
1 7
0 7
35 70


 
Арифметические алгоритмы (Теория чисел)Вывод формулыЦиклы
✓ 60✗ 108600лёгкаяВойти и решать
21883#21883
Введите с клавиатуры целое число X (|X| ≤ 109).
В первых трех строках выведите это число на экран в двоичной, восьмеричной, 16-ричной системах счисления.
В следующих двух строках выведите, поместится ли это число в ячейке типа byte и ячейке типа short ("YES"/"NO").
Запрещается использовать циклы и знания о том, сколько именно байт/бит памяти занимают переменные типа int, byte, short.
Пример ввода:
123
 
Пример вывода:
1111011
173
7B
YES
YES
 
Пример ввода:
40000
 
Пример вывода:
1001110001000000
116100
9C40
NO
NO

Разные системы счисленияСтрокиЦелые числа
✓ 102✗ 54400лёгкаяВойти и решать
Число с максимальным количеством делителей#21834
Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно  число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод

Вывод
5
22790
94
66
18
18
 22790
2
21
46 
 21
 
Алгоритмы обработкиЗадачи на процедуры и функцииПростые числа и разложение на множители
✓ 112✗ 236700средняяВойти и решать
ABCD-код#21810
Вася часто ходит в гости к Пете. Для того, чтобы попасть к Пете во двор, надо ввести код,
состоящий из четырех цифр. Обычно друзья ходили вместе, но в этот раз Вася пришел один, а
Петя ждет его у себя.
Вася не помнит код, но у него есть несколько вариантов. Кроме того, Васе почему-то запомнился
факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа,
состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код
представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда AB2+CD2 имеет
остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку
282 + 432 = 2633 = 376 · 7 + 1, а 8243 — нет, поскольку 822 + 432 = 8573 = 1224 · 7 + 5.
У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие
из вариантов могут быть кодом от входа в Петин двор.

Формат входных данных
В первой строке  находится число t (1 ≤ t ≤ 10 000) — число вариантов кода,
которые помнит Вася. В следующих t строках содержится по четыре цифры — варианты кода.
Формат выходных данных
В ответе выведите t строк. В i-й строке выведите «YES», если i-й код может быть кодом
для входа в Петин двор, иначе выведите «NO».
Вычисление по заданной формулеОстатки
✓ 149✗ 143500лёгкаяВойти и решать
Простые числа - 1#21768
Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k.

Входные данные 
Число k.

Выходные данные 
Вывести число - количество простых чисел, удовлетворяющих условию задачи. Если таких чисел нет то вывести слово Absent.

Примеры
№ Входные данные Выходные данные
1 1 266
2 0 Absent
Простые числа и разложение на множители
✓ 794✗ 1 382400лёгкаяВойти и решать
Постулат Бертрана#21767

Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого \(n > 1\) найдется простое число p в интервале \(n < p < 2n\). Такая гипотеза была выдвинута в 1845 году французским математиком Джозефом Бертраном (проверившим ее до \(n=3000000\)) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала \(n < p < 2n\).

Напомним, что число называется простым, если оно делится только само на себя и на единицу

Входные данные
Целое число n (\(2 <= n <= 50000\)).

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

 
Примеры
№ Входные данные Выходные данные
1 3000 353
Простые числа и разложение на множители
✓ 630✗ 1 075500лёгкаяВойти и решать
Максимальная цифра в восьмеричной СС#21763
Дано натуральное число N . Необходимо найти максимальную цифру данного числа при его записи в восьмеричной системе счисления.

Входные данные
На вход подается натуральное число N (\(N<=255\)).

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

 

Примеры
№ Входные данные Выходные данные
1 255 7

 

Разные системы счисления
✓ 506✗ 350300лёгкаяВойти и решать
Поделиться
Класснуть