0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
|
|
Олимпиадная задача про НОД06.06.2023, 18:15. Показов 3014. Ответов 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 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
|
|
06.06.2023, 19:00 | |
Как считается количество операций? Когда мы вычитаем числа (делаем замену) - это 1 операция?
Вычисление НОД не считается операцией? И что значит "делал в тупую"? Свои попытки можно продемонстрировать. Также в условии видимо число-ограничение не 1012, а 1012 (скорей всего).
1
|
![]() 583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
|
||||||||||||
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 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
|
|||||||||||||
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 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
|
||||||
06.06.2023, 20:26 | ||||||
Tonendd, для начала лучше (наверно) использовать unsigned long long вместо long long (но это не точно).
И замечание Tanya2007, возможно, не лишено смысла. Но в любом случае ошибка в логике плюс не учтен приоритет операций (строка №15 кода). Должно быть что-то вроде
0
|
place status here
![]() 3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
|
|||||||||||
06.06.2023, 20:57 | |||||||||||
Не за что. Ошибки вроде быть не должно.
Если только убрать слагаемое
Как вариант, при проверке может происходить (каким-то образом) не целочисленное деление и из-за этого результат выходит ошибочным (но это лишь предположение).
0
|
732 / 693 / 110
Регистрация: 29.05.2015
Сообщений: 4,187
|
||||||
07.06.2023, 11:04 | ||||||
Попробуй без рекурсии:
1
|
07.06.2023, 12:42 | |
Не по теме: alexu_007, ТС говорил, что у него выскакивает ошибка вычислений (по какой-то не очень понятной причине).
0
|
07.06.2023, 12:42 | |
Помогаю со студенческими работами здесь
20
C++. Олимпиадная задача
Олимпиадная задача Задача на дп (олимпиадная) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Опции темы | |
|
Новые блоги и статьи
![]() |
||||
Создаем RESTful API с Laravel
Jason-Webb 28.04.2025
REST (Representational State Transfer) — это архитектурный стиль, который определяет набор принципов для создания веб-сервисов. Этот подход к построению API стал стандартом де-факто в современной. . .
|
Дженерики в C# - продвинутые техники
stackOverflow 28.04.2025
История дженериков началась с простой идеи — создать механизм для разработки типобезопасного кода без потери производительности. До их появления программисты использовали неуклюжие преобразования. . .
|
Тестирование в Python: PyTest, Mock и лучшие практики TDD
py-thonny 28.04.2025
Тестирование кода играет весомую роль в жизненном цикле разработки программного обеспечения. Для разработчиков Python существует богатый выбор инструментов, позволяющих создавать надёжные и. . .
|
Работа с PDF в Java с iText
Javaican 28.04.2025
Среди всех форматов PDF (Portable Document Format) заслуженно занимает особое место. Этот формат, созданный компанией Adobe, превратился в универсальный стандарт для обмена документами, не зависящий. . .
|
Динамические массивы в C++ - создание и использование
NullReferenced 27.04.2025
Динамические массивы представляют собой один из фундаментальных инструментов программирования на C++, позволяющий создавать структуры данных, размер которых определяется во время выполнения. . .
|
Асинхронный JavaScript: Промисы, Async/Await и Fetch API
Reangularity 27.04.2025
Пользователь заходит на веб-страницу, нажимает кнопку и. . . ничего не происходит. Сайт словно замер. Через несколько секунд всё внезапно оживает, но пользователь уже успел закрыть вкладку. Знакомая. . .
|
Management on GitLab and repository management in Visual Studio code
jigi33 27.04.2025
- repo management on GitLab
- CI/ CD in GitLab
- VCS repository management in Visual Studio code
(see attachments)
|
Kanban или Scrum - что выбрать?
EggHead 27.04.2025
Kanban и Scrum — уже много лет удерживают лидирующие позиции среди гибких подходов. Руководители проектов и команды разработчиков то и дело сталкиваются с дилеммой: какой из этих двух методов выбрать. . .
|
Кастомные Middleware на C# в ASP.NET Core
UnmanagedCoder 27.04.2025
Разработка веб-приложений сегодня мало напоминает монолитное программирование прошлых лет. На смену громоздким блокам кода пришла модульная архитектура, где каждый компонент выполняет строго. . .
|
Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint
run.dev 26.04.2025
JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
|