Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы
    НОД и алгоритм Евклида(45 задач)
    Системы счисления(36 задач)
    "Длинная" арифметика(58 задач)
    Простые числа и разложение на множители(45 задач)
    Остатки(21 задач)
    Быстрое возведение в степень(3 задач)
    Быстрое преобразование Фурье(3 задач)
---> 240 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
#146
Сложить две дроби
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Даны две рациональные дроби: a/b и c/d. Сложите их и результат представьте в виде несократимой дроби m/n.

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

Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.

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

Программа должна вывести 2 натуральных числа m и n такие, что m/n=a/b+c/d и дробь m/n – несократима.

Примеры
Входные данные
1 3 1 2
Выходные данные
5 6
#147
Алгоритм Евклида
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

По данным натуральным числам n и m найдите их наибольший общий делитель.

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

Программа получает на вход 2 натуральных числа m и n. Числа m и n не превосходят 109.

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

Программа должна вывести наибольший общий делитель двух данных чисел.

Примеры
Входные данные
6
5
Выходные данные
1
Входные данные
12
14
Выходные данные
2
#148
Разложение на простые
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Программа получает на вход одно число n<231.

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

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

Примеры
Входные данные
6
Выходные данные
2 3
#152
Гипотеза Гольдбаха
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.

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

Программа получает на вход одно натуральное четное число n (3<n<2*105).

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

Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.

Примеры
Входные данные
4
Выходные данные
2 2
Входные данные
6
Выходные данные
3 3
#154
НОД
  
Максимальное время работы на одном тесте: 1 секунда

Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель.

Примечание. В программе запрещается использовать циклы.

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

Вводятся два натуральных числа A и B (A, B ≤ 109).

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

Требуется вывести НОД A и B.

Примеры
Входные данные
12 42
Выходные данные
6
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест