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

@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++
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);     //вернет НОД
}

@gunslinger · 06.06.2023, 19:00

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

@Tanya2007 · 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;

@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++
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

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

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

@Tanya2007 · 06.06.2023, 20:09

Tonendd,

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

@Tonendd · 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;
}

@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

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

Code
1
num - 1

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

Code
1
min / num

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

@alexu_007 · 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));
}

@gunslinger · 07.06.2023, 12:42

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Исключения в 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, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .

@Tonendd 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

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

@Tonendd 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

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

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

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

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

@Tanya2007 587 / 226 / 69 Регистрация: 13.05.2020 Сообщений: 405
	06.06.2023, 20:25
	Tonendd, если не секрет, где тесты проводите? 0

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

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

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

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