0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
|
|
Олимпиадная задача про НОД06.06.2023, 18:15. Показов 3027. Ответов 34
Метки нет Все метки)
(
Леброну на уроке рассказали про НОД (наибольший общий делитель) и дали задачку.
В задачке давалось два числа x и y. Леброну надо было повторять следующую операцию, пока x и y больше или равны 1. Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y). В задаче надо найти количество операций, которые будут сделаны. Входные данные Первая строка содержит два целых числа: x,y (1≤x,y≤1012). Выходные данные Выведите ответ на задачу. Пример входные данные 30 27 выходные данные 9 Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет
0
|
06.06.2023, 18:15 | |
Ответы с готовыми решениями:
34
Задача про НОД
|
place status here
![]() 3180 / 2208 / 640
Регистрация: 20.07.2013
Сообщений: 5,897
|
|
06.06.2023, 19:00 | |
Как считается количество операций? Когда мы вычитаем числа (делаем замену) - это 1 операция?
Вычисление НОД не считается операцией? И что значит "делал в тупую"? Свои попытки можно продемонстрировать. Также в условии видимо число-ограничение не 1012, а 1012 (скорей всего).
1
|
![]() 587 / 226 / 69
Регистрация: 13.05.2020
Сообщений: 405
|
||||||||||||
06.06.2023, 19:12 | ||||||||||||
Его оригинальное решение через разность двух чисел (полагаю именно оно нужно вам):
1
|
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
|
|
06.06.2023, 19:32 [ТС] | |
gunslinger, одна операция это:
Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y). В тупую я имел ввиду ровно так, как по условию. Вычитать НОД, прибавлять 1 к счетчику пока каждое из чисел больше или равно 1. Такое решение работает медленно и не заходит по времени. Да, 10^12
0
|
place status here
![]() 3180 / 2208 / 640
Регистрация: 20.07.2013
Сообщений: 5,897
|
|||||||||||||
06.06.2023, 19:51 | |||||||||||||
Tonendd, понятно. Tanya2007, как вариант (что-то такое и использовал).
Код для НОД можно взять отсюда Нахождения НОД (аналогичен примеру из поста №2 в этой теме). В итоге получилось так:
тут
или здесь
1
|
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
|
||||||
06.06.2023, 20:18 [ТС] | ||||||
Tanya2007 я просто взял код от gunslinger и добавил ввод и вывод.
0
|
place status here
![]() 3180 / 2208 / 640
Регистрация: 20.07.2013
Сообщений: 5,897
|
||||||
06.06.2023, 20:26 | ||||||
Tonendd, для начала лучше (наверно) использовать unsigned long long вместо long long (но это не точно).
И замечание Tanya2007, возможно, не лишено смысла. Но в любом случае ошибка в логике плюс не учтен приоритет операций (строка №15 кода). Должно быть что-то вроде
0
|
place status here
![]() 3180 / 2208 / 640
Регистрация: 20.07.2013
Сообщений: 5,897
|
|||||||||||
06.06.2023, 20:57 | |||||||||||
Не за что. Ошибки вроде быть не должно.
Если только убрать слагаемое
Как вариант, при проверке может происходить (каким-то образом) не целочисленное деление и из-за этого результат выходит ошибочным (но это лишь предположение).
0
|
732 / 693 / 110
Регистрация: 29.05.2015
Сообщений: 4,210
|
||||||
07.06.2023, 11:04 | ||||||
Попробуй без рекурсии:
1
|
07.06.2023, 12:42 | |
Не по теме: alexu_007, ТС говорил, что у него выскакивает ошибка вычислений (по какой-то не очень понятной причине).
0
|
07.06.2023, 12:42 | |
Помогаю со студенческими работами здесь
20
C++. Олимпиадная задача
Олимпиадная задача Задача на дп (олимпиадная) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Исключения в Java: советы, примеры кода и многое другое
Javaican 18.05.2025
Исключения — это объекты, созданные когда программа сталкивается с непредвиденной ситуацией: файл не найден, сетевое соединение разорвано, деление на ноль. . . Список можно продолжать до бесконечности. . . .
|
Как сделать SSO (Single Sign-On) в C# приложении
stackOverflow 18.05.2025
SSO — это механизм, позволяющий пользователю пройти аутентификацию один раз и получить доступ к нескольким приложениям без повторного ввода учетных данных. Вы наверняка сталкивались с ним, когда. . .
|
Kubernetes с Apache Flink для обработки данных в реальном времени
Mr. Docker 17.05.2025
Kubernetes — это целая философия управления распределёнными приложениями. В отличие от "примитивных" решений вроде Docker Swarm, K8s (как его ласково называют в тусовке DevOps-инженеров) предлагает. . .
|
Использование декораторов в Python
py-thonny 17.05.2025
Если вы когда-нибудь задумывались о том, как красиво расширить функциональность кода без лишней возни и дублирования, декораторы в Python — та самая волшебная палочка, которую вы искали. По сути, это. . .
|
Реализация многопоточных сетевых серверов на Python
py-thonny 16.05.2025
Когда сталкиваешься с необходимостью писать высоконагруженные сетевые сервисы, выбор технологии имеет критическое значение. Python, со своей элегантностью и высоким уровнем абстракции, может. . .
|
C# и IoT: разработка Edge приложений с .NET и Azure IoT
UnmanagedCoder 16.05.2025
Мир меняется прямо на наших глазах, и интернет вещей (IoT) — один из главных катализаторов этих перемен. Если всего десять лет назад концепция "умных" устройств вызывала скептические улыбки, то. . .
|
Гибридные квантово-классические вычисления: Примеры оптимизации
EggHead 16.05.2025
Гибридные квантово-классические вычисления — это настоящий прорыв в подходах к решению сложнейших вычислительных задач. Представьте себе союз двух разных миров: классические компьютеры, с их. . .
|
Использование вебсокетов в приложениях Java с Netty
Javaican 16.05.2025
HTTP, краеугольный камень интернета, изначально был спроектирован для передачи гипертекста с минимальной интерактивностью. Его главный недостаток в контексте современных приложений — это. . .
|
Реализация операторов Kubernetes
Mr. Docker 16.05.2025
Концепция операторов Kubernetes зародилась в недрах компании CoreOS (позже купленной Red Hat), когда команда инженеров искала способ автоматизировать управление распределёнными базами данных в. . .
|
Отражение в C# и динамическое управление типами
stackOverflow 16.05.2025
Reflection API в . NET — это набор классов и интерфейсов в пространстве имён System. Reflection, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .
|