0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9

Олимпиадная задача про НОД

06.06.2023, 18:15. Показов 3014. Ответов 34
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Леброну на уроке рассказали про НОД (наибольший общий делитель) и дали задачку.

В задачке давалось два числа x и y. Леброну надо было повторять следующую операцию, пока x и y больше или равны 1.

Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y).
В задаче надо найти количество операций, которые будут сделаны.

Входные данные
Первая строка содержит два целых числа: x,y (1≤x,y≤1012).

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

Пример
входные данные
30 27
выходные данные
9


Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.06.2023, 18:15
Ответы с готовыми решениями:

Задача про НОД
Найти наибольший общий делитель чисел m и n (количество знаков в числах не меньше 15) Не имею представления как оформить такую задачу,...

Задача про НОД
Есть такое условие: В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по...

Олимпиадная задачка про Роботов
Помогите решить не могу додуматься Роботы Кафедра ТМОИ создает роботов, которые могут находить и собирать мины с полей. Прежде чем...

34
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 18:55
Цитата Сообщение от Tonendd Посмотреть сообщение
Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет
Алгоритм Евклида:

C++
1
2
3
4
5
6
typedef unsigned int unint;
 
unint gcd(unint const a, unint const b)
{
    return b == 0 ? a : gcd(b, a % b);     //вернет НОД
}
1
place status here
 Аватар для gunslinger
3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
06.06.2023, 19:00
Как считается количество операций? Когда мы вычитаем числа (делаем замену) - это 1 операция?
Вычисление НОД не считается операцией?
И что значит "делал в тупую"? Свои попытки можно продемонстрировать.
Также в условии видимо число-ограничение не 1012, а 1012 (скорей всего).
1
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 19:12
Его оригинальное решение через разность двух чисел (полагаю именно оно нужно вам):

C++
1
2
3
4
5
6
7
8
9
10
unint gcd(unint const a, unint const b)
{
    unint temp;
    
    (a > b) ? (temp = a - b) : (temp = b - a);
    if (temp > b)
        return b == 0 ? a : gcd(temp, b);
    else
        return b == 0 ? a : gcd(b, temp);
}
Добавлено через 3 минуты
Цитата Сообщение от gunslinger Посмотреть сообщение
Также в условии видимо число-ограничение не 1012, а 1012 (скорей всего).
Тогда:
C++
1
typedef unsigned long long unint;
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
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 19:47
Цитата Сообщение от Tonendd Посмотреть сообщение
Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y).
В задаче надо найти количество операций, которые будут сделаны.
А если поделить числа на НОД и выбрать наименьшее из них, это должно быть ответом.
1
place status here
 Аватар для gunslinger
3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
06.06.2023, 19:51
Tonendd, понятно. Tanya2007, как вариант (что-то такое и использовал).

Код для НОД можно взять отсюда Нахождения НОД (аналогичен примеру из поста №2 в этой теме).

В итоге получилось так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ull;
//---------------------------------------------------------------------------
ull gcd (ull a, ull b)
{
  return a ? gcd(b % a, a) : b;
}
//---------------------------------------------------------------------------
ull func (ull x, ull y)
{
  ull min = x < y ? x : y, num = gcd(x, y);
  return (min + num - 1) / num;
}
Вариант использования (у меня билдер, поэтому в своей среде можно сделать "что-то похожее"):
C++
1
2
  ull num = 1000000000000ui64, x = random(num) + 1, y = random(num) + 1;
  Memo->Lines->Add("x = " + String(x) + ", y = " + String(y) + ", operations = " + String(func(x, y)));
Некоторые результаты:
тут
x = 13998021, y = 148491832, operations = 13998021
x = 114174669, y = 314253508, operations = 114174669
x = 28966086, y = 228590381, operations = 28966086
x = 367853687, y = 670934016, operations = 367853687
x = 703467337, y = 399338999, operations = 399338999
x = 383579048, y = 373565650, operations = 186782825
x = 707087018, y = 682201654, operations = 341100827
x = 605747305, y = 648306360, operations = 121149461
x = 196753597, y = 296537404, operations = 196753597
x = 600232260, y = 152762771, operations = 152762771
x = 133145169, y = 155227551, operations = 44381723
x = 620950504, y = 433067098, operations = 216533549
x = 581191600, y = 9595096, operations = 1199387
x = 632812143, y = 576322781, operations = 576322781
x = 515486644, y = 161793607, operations = 8515453
x = 562771813, y = 500097806, operations = 500097806
x = 598593722, y = 468471697, operations = 468471697
x = 412497604, y = 661550669, operations = 412497604
x = 678385806, y = 181322792, operations = 12951628
x = 52937141, y = 86415685, operations = 52937141
x = 160586467, y = 302153097, operations = 160586467
x = 442382035, y = 637467402, operations = 442382035
x = 284182502, y = 35781435, operations = 35781435
x = 28273345, y = 110332222, operations = 28273345
x = 105335244, y = 167122257, operations = 35111748
x = 541191659, y = 438584457, operations = 438584457
x = 156952393, y = 494522993, operations = 156952393
x = 123072932, y = 62403930, operations = 31201965
x = 515210731, y = 7343883, operations = 7343883
x = 43457016, y = 252075287, operations = 43457016
x = 360295627, y = 6940502, operations = 6940502

или
здесь
x = 75, y = 488, operations = 75
x = 905, y = 941, operations = 905
x = 453, y = 639, operations = 151
x = 294, y = 959, operations = 42
x = 756, y = 993, operations = 252
x = 451, y = 30, operations = 30
x = 783, y = 983, operations = 783
x = 298, y = 499, operations = 298
x = 487, y = 973, operations = 487
x = 52, y = 793, operations = 4
x = 542, y = 273, operations = 273
x = 569, y = 237, operations = 237
x = 753, y = 291, operations = 97
x = 296, y = 68, operations = 17
x = 316, y = 492, operations = 79
x = 434, y = 388, operations = 194
x = 276, y = 341, operations = 276
x = 106, y = 20, operations = 10
x = 192, y = 713, operations = 192
x = 198, y = 611, operations = 198
x = 562, y = 143, operations = 143
x = 670, y = 315, operations = 63
x = 281, y = 953, operations = 281
x = 231, y = 354, operations = 77
1
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
06.06.2023, 20:05  [ТС]
gunslinger, Tanya2007 спасибо большое за помочь, но увы неправильный ответ на одном из тестов (не знаю каком)
0
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 20:09
Tonendd,

тогда весь код в студию) видимо не учитывается какая-то исключительная ситуация.
0
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
06.06.2023, 20:18  [ТС]
Tanya2007 я просто взял код от gunslinger и добавил ввод и вывод.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
using namespace std;
 
long long gcd (long long a, long long b)
{
    return a ? gcd(b % a, a) : b;
}
 
int main()
{
    long long x, y;
    cin >> x >> y;
    long long num = gcd(x, y);
    cout << (x < y ? x : y + num - 1) / num;
}
0
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 20:21
Tonendd, может в тестах присутствуют отрицательные значения х и у? Тогда надо делать проверку на правильность ввода.
0
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
06.06.2023, 20:22  [ТС]
Tanya2007 вряд-ли, ограничения даны в условии
0
 Аватар для Tanya2007
583 / 219 / 68
Регистрация: 13.05.2020
Сообщений: 397
06.06.2023, 20:25
Tonendd, если не секрет, где тесты проводите?
0
place status here
 Аватар для gunslinger
3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
06.06.2023, 20:26
Tonendd, для начала лучше (наверно) использовать unsigned long long вместо long long (но это не точно).
И замечание Tanya2007, возможно, не лишено смысла.

Но в любом случае ошибка в логике плюс не учтен приоритет операций (строка №15 кода).
Должно быть что-то вроде
C++
15
    cout << ((x < y ? x : y) + num - 1) / num;
0
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
06.06.2023, 20:30  [ТС]
gunslinger ой, случайно) но ни то, ни другое не помогло Tanya2007 в группе кружка на кодфорсисе
0
place status here
 Аватар для gunslinger
3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
06.06.2023, 20:37
Тогда не знаю. Раз тест скрыт, то и гаданием на кофейной гуще заниматься смысла не вижу.
Там хоть суть проблемы показывается (ошибка вычислений, не проходит по времени либо еще что) или нет?
0
0 / 0 / 0
Регистрация: 06.06.2023
Сообщений: 9
06.06.2023, 20:39  [ТС]
Понятно. Ну ладно, все равно спасибо) Известно только что неправильный ответ и все
0
place status here
 Аватар для gunslinger
3180 / 2204 / 640
Регистрация: 20.07.2013
Сообщений: 5,885
06.06.2023, 20:57
Не за что. Ошибки вроде быть не должно.
Если только убрать слагаемое
Code
1
num - 1
и оставить лишь
Code
1
min / num
Только это влиять на результат не должно. Может, слагаемое изначально лишнее, но я пытался учесть "все случаи".
Как вариант, при проверке может происходить (каким-то образом) не целочисленное деление и из-за этого результат выходит ошибочным (но это лишь предположение).
0
732 / 693 / 110
Регистрация: 29.05.2015
Сообщений: 4,187
07.06.2023, 11:04
Попробуй без рекурсии:

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
quint64 nodd(quint64 a, quint64 b)
{
    quint64 c;
 
    while(b > 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
 
return a;
}
 
 
 
void Widget::press_pbtn_01()
{
    quint64 x1 = 30;
    quint64 x2 = 27;
    quint64 cx = 0;
 
    quint64 a;
 
    while(1)
    {
        a = nodd(x1, x2);
        x1 -= a;
        x2 -= a;
        cx++;
 
        if(x1 < 1 || x2 < 1) break;
    }
 
    ui->label->setText(QString::number(cx));
}
1
07.06.2023, 12:42

Не по теме:

alexu_007, ТС говорил, что у него выскакивает ошибка вычислений (по какой-то не очень понятной причине).
А у твоего кода в виду последовательных вычитаний и ограничения справа на входные данные в виде числа 1012 будет, скорей всего (как минимум), превышение лимита по времени.
И зачем каждый раз вычислять НОД? Он же вроде как не меняется.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
07.06.2023, 12:42
Помогаю со студенческими работами здесь

олимпиадная задачка про брак на заводе
Уважаемые программисты, вот еще одна задачка из серии олимпиадных. Может, она не такая сложная, но мне, как новичку в программировании,...

C++. Олимпиадная задача
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при...

Олимпиадная задача
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

Задача на дп (олимпиадная)
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

Новые блоги и статьи
Создаем 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 прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru