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

@Tonendd · Регистрация: 06.06.2023

Author24 — интернет-сервис помощи студентам

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

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

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

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

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

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

Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет

@Tanya2007 · 06.06.2023, 18:55

Сообщение от Tonendd

Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет

Алгоритм Евклида:

C++

typedef unsigned int unint;
 
unint gcd(unint const a, unint const b)
{
    return b == 0 ? a : gcd(b, a % b);     //вернет НОД
}

@gunslinger · 06.06.2023, 19:00

Как считается количество операций? Когда мы вычитаем числа (делаем замену) - это 1 операция?
Вычисление НОД не считается операцией?
И что значит "делал в тупую"? Свои попытки можно продемонстрировать.
Также в условии видимо число-ограничение не 1012, а 10¹² (скорей всего).

@Tanya2007 · 06.06.2023, 19:12

Его оригинальное решение через разность двух чисел (полагаю именно оно нужно вам):

C++

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;

@Tonendd · 06.06.2023, 19:32 **[ТС]**

gunslinger, одна операция это:
Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y).
В тупую я имел ввиду ровно так, как по условию. Вычитать НОД, прибавлять 1 к счетчику пока каждое из чисел больше или равно 1. Такое решение работает медленно и не заходит по времени.
Да, 10^12

@Tanya2007 · 06.06.2023, 19:47

Сообщение от Tonendd

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

А если поделить числа на НОД и выбрать наименьшее из них, это должно быть ответом.

@gunslinger · 06.06.2023, 19:51

Tonendd, понятно. Tanya2007, как вариант (что-то такое и использовал).

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

В итоге получилось так:

C++

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

@Tonendd · 06.06.2023, 20:05 **[ТС]**

gunslinger, Tanya2007 спасибо большое за помочь, но увы неправильный ответ на одном из тестов (не знаю каком)

@Tanya2007 · 06.06.2023, 20:09

Tonendd,

тогда весь код в студию) видимо не учитывается какая-то исключительная ситуация.

@Tonendd · 06.06.2023, 20:18 **[ТС]**

Tanya2007 я просто взял код от gunslinger и добавил ввод и вывод.

C++

#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;
}

@Tanya2007 · 06.06.2023, 20:21

Tonendd, может в тестах присутствуют отрицательные значения х и у? Тогда надо делать проверку на правильность ввода.

@Tonendd · 06.06.2023, 20:22 **[ТС]**

Tanya2007 вряд-ли, ограничения даны в условии

@Tanya2007 · 06.06.2023, 20:25

Tonendd, если не секрет, где тесты проводите?

@gunslinger · 06.06.2023, 20:26

Tonendd, для начала лучше (наверно) использовать unsigned long long вместо long long (но это не точно).
И замечание Tanya2007, возможно, не лишено смысла.

Но в любом случае ошибка в логике плюс не учтен приоритет операций (строка №15 кода).
Должно быть что-то вроде

C++

15	cout << ((x < y ? x : y) + num - 1) / num;

@Tonendd · 06.06.2023, 20:30 **[ТС]**

gunslinger ой, случайно) но ни то, ни другое не помогло

Tanya2007 в группе кружка на кодфорсисе

@gunslinger · 06.06.2023, 20:37

Тогда не знаю. Раз тест скрыт, то и гаданием на кофейной гуще заниматься смысла не вижу.
Там хоть суть проблемы показывается (ошибка вычислений, не проходит по времени либо еще что) или нет?

@Tonendd · 06.06.2023, 20:39 **[ТС]**

Понятно. Ну ладно, все равно спасибо) Известно только что неправильный ответ и все

@gunslinger · 06.06.2023, 20:57

Не за что. Ошибки вроде быть не должно.
Если только убрать слагаемое

Код

num - 1

и оставить лишь

Код

min / num

Только это влиять на результат не должно. Может, слагаемое изначально лишнее, но я пытался учесть "все случаи".
Как вариант, при проверке может происходить (каким-то образом) не целочисленное деление и из-за этого результат выходит ошибочным (но это лишь предположение).

@alexu_007 · 07.06.2023, 11:04

Попробуй без рекурсии:

C++ (Qt)

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));
}

@gunslinger · 07.06.2023, 12:42

Не по теме:

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

Новые блоги и статьи
NoSQL базы данных: что это такое и какие существуют bytestream 22.01.2025 В современную эпоху цифровой трансформации объемы данных растут экспоненциально, создавая новые вызовы для традиционных систем управления базами данных. NoSQL (Not Only SQL) представляет собой. . .	Обновление исследования от команды MCM (январь 2025 г.) Programma_Boinc 22.01.2025 Обновление исследования от команды MCM (январь 2025 г. ) Мы продолжаем изучать молекулярные сигнатуры, связанные с раком легких, с текущим фокусом на GCM1, факторе транскрипции, участвующем в. . .	Как работать с Kafka в Go (Golang) bytestream 22.01.2025 Apache Kafka представляет собой распределенную платформу потоковой передачи данных, которая произвела революцию в области обработки событий и интеграции микросервисов. Эта система, изначально. . .	Как использовать RabbitMQ в Go (Golang) bytestream 22.01.2025 RabbitMQ представляет собой надежный и широко используемый брокер сообщений, который играет ключевую роль в построении современных распределенных систем и микросервисной архитектуры. В основе работы. . .	Как преобразовать список списков в простой список в Python bytestream 22.01.2025 При работе с Python разработчики часто сталкиваются с необходимостью обработки сложных структур данных, среди которых особое место занимают вложенные списки. Эти структуры представляют собой списки,. . .	Что такое GUID / UUID и как их создать bytestream 22.01.2025 В мире разработки программного обеспечения существует постоянная потребность в уникальной идентификации объектов, записей и ресурсов. Эта задача становится особенно актуальной в распределенных. . .
Как добавить пустую директорию в репозиторий Git bytestream 22.01.2025 При работе с системой контроля версий Git разработчики часто сталкиваются с ситуацией, когда необходимо сохранить пустую директорию в репозитории. Данная задача может показаться простой на первый. . .	Как валидировать адрес email в JavaScript bytestream 22.01.2025 JavaScript, как основной язык веб-разработки, предоставляет разработчикам множество инструментов для реализации эффективной валидации email-адресов. От простых встроенных решений до сложных. . .	Как заменить все вхождения подстроки в JavaScript bytestream 22.01.2025 Строки в JavaScript представляют собой неизменяемые последовательности символов, что делает их обработку особенно интересной с точки зрения оптимизации и выбора правильного подхода к решению задач. . . .	Управление версиями пакетов в Node.js. В чем разница между тильдой (~) и кареткой (^) в package.json bytestream 22.01.2025 В современной разработке программного обеспечения управление версиями пакетов играет ключевую роль в обеспечении стабильности и надежности проектов. Node. js, как одна из самых популярных платформ для. . .	Аутентификация на сайте с помощью формы bytestream 21.01.2025 В современном цифровом мире безопасная аутентификация становится краеугольным камнем защиты веб-приложений и пользовательских данных. Каждый день миллионы людей используют различные онлайн-сервисы,. . .	Как получить индекс в цикле for в Python bytestream 21.01.2025 При работе с коллекциями данных в Python часто возникает необходимость не только получить доступ к элементам последовательности, но и знать их позицию в процессе итерации. Индексация в циклах. . .

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9
		1
	Олимпиадная задача про НОД 06.06.2023, 18:15. Показов 2857. Ответов 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

@gunslinger случайный прохожий 3071 / 2107 / 630 Регистрация: 20.07.2013 Сообщений: 5,656
	06.06.2023, 19:00	3
	Как считается количество операций? Когда мы вычитаем числа (делаем замену) - это 1 операция? Вычисление НОД не считается операцией? И что значит "делал в тупую"? Свои попытки можно продемонстрировать. Также в условии видимо число-ограничение не 1012, а 10¹² (скорей всего). 1

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9
	06.06.2023, 19:32 [ТС]	5
	gunslinger, одна операция это: Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y). В тупую я имел ввиду ровно так, как по условию. Вычитать НОД, прибавлять 1 к счетчику пока каждое из чисел больше или равно 1. Такое решение работает медленно и не заходит по времени. Да, 10^12 0

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	06.06.2023, 19:47	6
	Сообщение от Tonendd Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y). В задаче надо найти количество операций, которые будут сделаны. А если поделить числа на НОД и выбрать наименьшее из них, это должно быть ответом. 1

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

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	06.06.2023, 20:09	9
	Tonendd, тогда весь код в студию) видимо не учитывается какая-то исключительная ситуация. 0

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	06.06.2023, 20:21	11
	Tonendd, может в тестах присутствуют отрицательные значения х и у? Тогда надо делать проверку на правильность ввода. 0

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9
	06.06.2023, 20:22 [ТС]	12
	Tanya2007 вряд-ли, ограничения даны в условии 0

@Tanya2007 419 / 206 / 64 Регистрация: 13.05.2020 Сообщений: 385
	06.06.2023, 20:25	13
	Tonendd, если не секрет, где тесты проводите? 0

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9
	06.06.2023, 20:30 [ТС]	15
	gunslinger ой, случайно) но ни то, ни другое не помогло Tanya2007 в группе кружка на кодфорсисе 0

@gunslinger случайный прохожий 3071 / 2107 / 630 Регистрация: 20.07.2013 Сообщений: 5,656
	06.06.2023, 20:37	16
	Тогда не знаю. Раз тест скрыт, то и гаданием на кофейной гуще заниматься смысла не вижу. Там хоть суть проблемы показывается (ошибка вычислений, не проходит по времени либо еще что) или нет? 0

@Tonendd 0 / 0 / 0 Регистрация: 06.06.2023 Сообщений: 9
	06.06.2023, 20:39 [ТС]	17
	Понятно. Ну ладно, все равно спасибо) Известно только что неправильный ответ и все 0

@gunslinger случайный прохожий 3071 / 2107 / 630 Регистрация: 20.07.2013 Сообщений: 5,656
	06.06.2023, 20:57	18
	Не за что. Ошибки вроде быть не должно. Если только убрать слагаемое Код num - 1 и оставить лишь Код min / num Только это влиять на результат не должно. Может, слагаемое изначально лишнее, но я пытался учесть "все случаи". Как вариант, при проверке может происходить (каким-то образом) не целочисленное деление и из-за этого результат выходит ошибочным (но это лишь предположение). 0

@gunslinger
	07.06.2023, 12:42 Олимпиадная задача про НОД #20
	Не по теме: alexu_007, ТС говорил, что у него выскакивает ошибка вычислений (по какой-то не очень понятной причине). А у твоего кода в виду последовательных вычитаний и ограничения справа на входные данные в виде числа 10¹² будет, скорей всего (как минимум), превышение лимита по времени. И зачем каждый раз вычислять НОД? Он же вроде как не меняется. 0