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

114 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Обработка вводимых чисел - 13#34804
Дана последовательность целых чисел. Найти в ней минимальное число, не кратное 3. В последовательности имеется как минимум одно число не кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности, а затем N целых чисел, по одному в строке.
Выходные данные: Выведите ответ на задачу

Примеры
№ Входные данные Выходные данные
1 7
4
6
5
-3
-4
3
-2		 -4
 
 
Алгоритмы обработкиОстаткиЦикл for
✓ 151✗ 275500лёгкаяВойти и решать
Обработка вводимых чисел - 12#34803
Дана последовательность целых чисел. Найти в ней минимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности (N - положительное число, не превышающее 100) , а затем N целых чисел, по одному в строке (каждое число не превышает по модулю 1000).
Выходные данные: Выведите ответ на задачу

Примеры
№ Входные данные Выходные данные
1 7
4
6
5
-3
-4
3
-2		 -3
 
 
Алгоритмы обработкиОстаткиЦикл for
✓ 130✗ 184500лёгкаяВойти и решать
Обработка вводимых чисел - 10#34801
Дана последовательность целых чисел. Найти в ней максимальное число, кратное 3. В последовательности имеется как минимум одно число кратное 3

Входные данные: В первой строке вводится число N - количество чисел в последовательности, а затем N целых чисел, по одному в строке.
Выходные данные: Выведите ответ на задачу

Примеры
№ Входные данные Выходные данные
1 7
4
6
5
-3
-4
3
-2		 6
 
 
Алгоритмы обработкиОстаткиЦикл for
✓ 64✗ 112600лёгкаяВойти и решать
Выбрать числа Фибоначчи#33723
Дан массив чисел. Необходимо записать в другой массив, все числа Фибоначчи исходного массива. Если в исходном массиве нет чисел Фибоначчи, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N чисел – элементы массива (целые неотрицательные числа, не превышающие 1000). Гарантируется, что 0 < N ≤ 10000.

Выходные данные
Программа должна вывести в одну строчку все элементы построенного массива, разделив их пробелами. Если ни одного подходящего элемента в массиве не было, программа должна вывести число 0.
 
Примеры
№ Входные данные Выходные данные
1 6
4 14 5 8 12 13		 5 8 13
Алгоритмы обработкиАрифметические алгоритмы (Теория чисел)
✓ 2 376✗ 3 998500лёгкаяВойти и решать
Выбрать простые#33722
Дан массив чисел. Необходимо записать в другой массив все простые числа исходного массива. Если в исходном массиве нет простых чисел, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N натуральных чисел – элементы массива (все числа не превышают 1000). Гарантируется, что 0 < N ≤ 10000.

Выходные данные
Программа должна вывести в одну строчку все элементы нового массива, разделяя их пробелами. Если ни одного подходящего элемента в массиве не было, программа должна вывести число 0.
 
Примеры
№ Входные данные Выходные данные
1 6
1 2 3 4 5 6		 2 3 5
Алгоритмы обработкиПростые числа и разложение на множители
✓ 2 738✗ 7 155400лёгкаяВойти и решать
Функция Эйлера#33687
Дано натуральное число \(n  <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

Входные данные
На вход подается натуральное число n.

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

 

Примеры
№ Входные данные Выходные данные
1 2 1
Функция Эйлера
✓ 255✗ 442500лёгкаяВойти и решать
И снова яблоки!#33599

n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.
Запрещено использовать какие-либо алгоритмические конструкции (if, while, for и т.п.), кроме арифметических операций 

Входные данные: Программа получает на вход числа n и k (по одному в строке).
Выходные данные: Программа должна вывести количество школьников, которым достанется яблок меньше, чем некоторым из их товарищей.
Примеры
№ Входные данные Выходные данные
1 7
30		 5
Остатки
✓ 96✗ 364600лёгкаяВойти и решать
Число 2 в степени N#33587
Дано натуральное число N (вводится с клавиатуры). Вычислите \(2^N\). Выведите на экран вычисленное значение (\(1<=N<=15\)).


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

Выходные данные
Выведите на экран результат выражения \(2^N\).
 
 
Примеры
№ Входные данные Выходные данные
1 3 8
Быстрое возведение в степеньЛинейные алгоритмы
✓ 17 526✗ 25 494100лёгкаяВойти и решать
Гипотеза Гольдбаха#33572
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.

Входные данные 
Программа получает на вход одно натуральное четное число n (\(3<n<2 \cdot 10^5\)).

Выходные данные 
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.
 
Примеры
№ Входные данные Выходные данные
1 4 2 2
2 6 3 3
Простые числа и разложение на множители
✓ 495✗ 673400лёгкаяВойти и решать
Проверка на простоту#33571
Проверьте, является ли число простым.

Входные данные 
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.

Выходные данные 
Необходимо вывести  строку prime, если число простое, или composite, если число составное.
 
Примеры
№ Входные данные Выходные данные
1 5 prime
Простые числа и разложение на множители
✓ 1 019✗ 2 995300лёгкаяВойти и решать
Расширенный алгоритм Евклида#31903
Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.
 
Входные данные 
Натуральные числа и не превышают по модулю 10000.

Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 1 2 3 1 1 1
2 10 6 8 2 2 -2
Расширенный алгоритм Евклида
✓ 402✗ 990600лёгкаяВойти и решать
Быстрое возведение в степень#31901
Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\)  при четном n, 
\(a^n=a \cdot a^{n-1}\)  при нечетном n.
 
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .
 
Входные данные
Вводится вещественное число a и целое число n.
 
Выходные данные 
Выведите ответ на задачу, с точностью 6 знаков после запятой.
 
Нельзя использовать стандартное возведение в степень.
 

 

Примеры
№ Входные данные Выходные данные
1 2
7		 128
2
1.00001
100000
 2.71827

 
Быстрое возведение в степень
✓ 371✗ 1 140600лёгкаяВойти и решать
Кролик Клевер#31884
Кролик Клевер очень любит яблоки. Также он любит угощать яблоками своих друзей. У Кролика N друзей. Он собрал в саду K яблок и хочет их поделить поровну между своими друзьями, неделящийся остаток он оставит в корзинке. Сколько яблок достанется каждому другу и сколько яблок у него останется в корзине?
Помогите Кролику Клеверу посчитать эту информацию. Напишите для него программу.

Формат входных данных
Программа получает на вход два числа: N - количество друзей у кролика (не более 1000), K - количество яблок (не более 1000000). Каждое число записано в отдельной строке.

Формат выходных данных
Необходимо вывести в первой строке число яблок, которые достанутся каждому другу. Во второй строке - число яблок, которые останутся в корзинке.
Линейные алгоритмыОстатки
✓ 7 606✗ 7 417200лёгкаяВойти и решать
Возведение a в степень b по модулю c#31881
Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\) ). Вычислите a в степени b по модулю c  (\(a^b mod \ c\)).

Входные данные
На вход подаются три целых неотрицательных числа, разделенных одним пробелом.

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

 

Примеры
№ Входные данные Выходные данные
1 2 10 1000 24
Быстрое возведение в степень
✓ 348✗ 843600лёгкаяВойти и решать
Сложить две дроби#31872
Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).
 
Входные данные 
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.
 
Выходные данные 
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.
 
Примеры
№ Входные данные Выходные данные
1  1 3 1 2 5 6
НОД и алгоритм Евклида
✓ 1 118✗ 1 731400лёгкаяВойти и решать
Применение Малой Теоремы Ферма#31866
Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).


Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

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

 

Примеры
№ Входные данные Выходные данные
1 2 5 3
 
Малая теорема Ферма
✓ 263✗ 1 128600лёгкаяВойти и решать
Сумма функции Эйлера#31850
Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\),  где  \(p\)  - простое число, \(\alpha\)-  натуральное число.

Входные данные
В одной строке через пробел подаются два числа \(p\) и \(\alpha\)  (\(p <=11,   \alpha  <=60 \)).

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

 

Пример
№ Входные данные Выходные данные
1 2 2 4
Функция Эйлера
✓ 199✗ 389400лёгкаяВойти и решать
Несложная сортировка#30779
Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.
 
Задано n чисел a1, a2, ..., an. Необходимо вычислить последовательность bi по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность bi по неубыванию.
 
Входные данные
Первая строка содержит три целых числа: n, k1, k2 (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: ai (\(1 <= a_i <= 10^9\)).
 
Выходные данные
В ответе выведите n чисел – bi в требуемом порядке.
 

 

Примеры
№ Входные данные Выходные данные
1
9 10 10
1 2 3 4 5 6 7 9 8
 1 4 9 16 25 36 49 64 81
2
10 2 2
1 2 4 8 16 32 64 128 256 512
 1 1 1 1 1 1 1 1 1 1
Разные системы счисления
✓ 140✗ 94600лёгкаяВойти и решать
Апельсины#30777
Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов. Она хочет разрезать каждый апельсин на одинаковое число равных долек так, чтобы их можно было распределить между гостями (сама Катя апельсины есть не будет), и всем досталось одинаковое количество долек.

Напишите программу, которая вычисляет минимальное количество долек, на которое необходимо разрезать каждый апельсин, чтобы были выполнены указанные выше условия.
 
Входные данные 
Входная строка содержит два положительных целых числа n и m (\(1 <= n, m <= 10^9\)).

Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 2 5 2
2 2 4 1
НОД и алгоритм Евклида
✓ 778✗ 1 703500лёгкаяВойти и решать
Несложное вычисление#30775
Задано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.
 
Например, пусть \(n = 239\), \(k = 8\). Тогда представление числа n в восьмеричной системе счисления — \(357\), а ответ на задачу равен \(3 \cdot 5 \cdot 7 ? (3 + 5 + 7) = 90\).
 
 
Входные данные
Строка содержит два натуральных числа: n и k (\(1 <= n <= 10^9\), \(2 <= k <= 10\)). Оба этих числа заданы в десятичной системе счисления.
 
Выходные данные
Выведите ответ на задачу (в десятичной системе счисления).
 

 

Примеры
№ Входные данные Выходные данные
1 239 8 90
2 1000000000 7 -34
Разные системы счисления
✓ 333✗ 187400лёгкаяВойти и решать
Поделиться
Класснуть