Олимпиадная задача про НОД - C/C++ - Ответ 16934925

@gunslinger · 09.06.2023, 12:43

Да, я про пост №25. Благодарю за информацию.
Значит, моя идея про проверку, является ли выражение (|x - y| / НОД) простым числом, не работает в принципе?
Тогда еще вопрос, касающийся алгоритма:

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

После вычитания 20 НОД становится равным 560 и остаётся таким в течение 101681 шагов

Как удалось определить значение количества шагов - по какой-то формуле или просто следуя "точному алгоритму задачи" (поэтапно вычитая НОД и высчитывая его значение повторно)?

Добавлено через 1 час 19 минут
Кажется, я понял. Если выражение

|x - y| / НОД

является простым числом, то нужно еще проверить условие

min(x, y) >= |x - y|

Если оно выполняется, то при вычитании НОД из x и y на каком-то этапе (или сразу; количество шагов вроде легко узнать), мы получим, что

min(x, y) = |x - y|

Тогда

max(x, y) = 2*|x - y|

и

НОД(x, y) = |x - y|

Вроде так. Верно?

Добавлено через 45 минут
Только не min(x, y) = |x - y| и max(x, y) = 2*|x - y|, а min(x, y) кратно |x - y| и max(x, y) кратно 2*|x - y|.

Добавлено через 35 минут
Код (с промежуточными выводами) двух функций (через деление на НОД и без):

C++

ull func (ull x, ull y)  // алгоритм через сокращение x и y на НОД
{
  Form1->Memo->Text = "";
  ull num, count = 0;
  bool num_was_one = 0;
  do
  {
    num = gcd(x, y);
    Form1->Memo->Lines->Add("count = " + String(count) +
                            "   :::::   gcd(" + String(x) + ", " + String(y) + ") = " + String(num) +
                            "   :::::   (x / gcd) and (y / gcd) = " + String(x / num) + " and " + String(y / num));
    x /= num, y /= num;
    x--, y--, count++;
    if (num == 1 && !num_was_one)
    {
      ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min, tmp;
      if (dif == 1 || is_prime(dif))
      {
        if (min >= dif)
          tmp = min - (min / dif) * dif, x -= tmp, y -= tmp, count += tmp / num;
        else
          return count + min;
      }
    }
    num_was_one = (num == 1);
  } while(x > 0 && y > 0);
  return count;
}
//---------------------------------------------------------------------------
ull func2 (ull x, ull y)  // "точный" алгоритм (как в задаче)
{
  Form1->Memo->Text = "";
  ull num, num2 = 0, count = 0;
  bool same_prev_num = 0;
  do
  {
    num = gcd(x, y);
    same_prev_num = (num2 == num);
    Form1->Memo->Lines->Add("count = " + String(count) +
                            "   :::::   gcd(" + String(x) + ", " + String(y) + ") = " + String(num) +
                            "   :::::   (x / gcd) and (y / gcd) = " + String(x / num) + " and " + String(y / num));
    x -= num, y -= num, count++;
    if (!same_prev_num)
    {
      ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min, tmp;
      if (dif == 1 || is_prime(dif / num))
      {
        if (min >= dif)
          tmp = min - (min / dif) * dif, x -= tmp, y -= tmp, count += tmp / num;
        else
          return count + min / num;
      }
    }
    num2 = num;
  } while(x > 0 && y > 0);
  return count;
}

Соответствующие результаты:

count = 0 ::::: gcd(408564263, 584375703) = 1 ::::: (x / gcd) and (y / gcd) = 408564263 and 584375703
count = 1 ::::: gcd(408564262, 584375702) = 2 ::::: (x / gcd) and (y / gcd) = 204282131 and 292187851
count = 2 ::::: gcd(204282130, 292187850) = 10 ::::: (x / gcd) and (y / gcd) = 20428213 and 29218785
count = 3 ::::: gcd(20428212, 29218784) = 28 ::::: (x / gcd) and (y / gcd) = 729579 and 1043528
count = 4 ::::: gcd(729578, 1043527) = 1 ::::: (x / gcd) and (y / gcd) = 729578 and 1043527
count = 101684 ::::: gcd(627898, 941847) = 313949 ::::: (x / gcd) and (y / gcd) = 2 and 3
count = 101685 ::::: gcd(1, 2) = 1 ::::: (x / gcd) and (y / gcd) = 1 and 2
---------------------------------------------------------------------------
total count = 101686 (x = 408564263, y = 584375703)

и

count = 0 ::::: gcd(408564263, 584375703) = 1 ::::: (x / gcd) and (y / gcd) = 408564263 and 584375703
count = 1 ::::: gcd(408564262, 584375702) = 2 ::::: (x / gcd) and (y / gcd) = 204282131 and 292187851
count = 2 ::::: gcd(408564260, 584375700) = 20 ::::: (x / gcd) and (y / gcd) = 20428213 and 29218785
count = 3 ::::: gcd(408564240, 584375680) = 560 ::::: (x / gcd) and (y / gcd) = 729579 and 1043528
count = 101684 ::::: gcd(351622880, 527434320) = 175811440 ::::: (x / gcd) and (y / gcd) = 2 and 3
count = 101685 ::::: gcd(175811440, 351622880) = 175811440 ::::: (x / gcd) and (y / gcd) = 1 and 2
---------------------------------------------------------------------------
total count = 101686 (x = 408564263, y = 584375703)

Вернуться к обсуждению:
Олимпиадная задача про НОД C/C++

Следующий ответ

Другие темы раздела
C/C++ Реализация LIKE как в VB или SQL на С++ или Си https://www.cyberforum.ru/ c-cpp/ thread3110295.html Мое почтение, джентльмены. Нужна быстрая реализация LIKE как в VB или SQL (алгоритм аналогичный) на С++ или Си. Из вменяемого нашел только часть алгоритма (ссылка не вставляется, напишу ниже). А так же в Win32 SymMatchString(), которая на порядок медленее чем моя текущая реализация. Не хочу колхозить свой велосипед, возможно кто-то сможет поделится проверенным алгоритмом. Добавлено...	Компиляция под 32 битные системы C/C++ Здравствуйте, пишу игру на с++ с помощью Sublime Text, make и g++ компилятора. Мне нужно каким то образом собрать exe под 32 битные системы, возможно дело не в разрядности, в ошибке пишет "Эта версия '%1' не совместима с версией Windows" (на другом компьютере с 32 битами, на моём 64 бита и всё работает). Вычитал, что для компиляции на 32 бита надо использовать -m32, но при его использовании...
C/C++ Нужна проверка вводимых данных Ребята опытные, помогите с проверкой вводимого числа double. При вводе в double 22ю3, запишется 22, через запятую тоже самое запишется и если писать буквы он ничего не запишет, но и ничего не поменяет(сделано через do/while). Как сделать проверку на такой случай? Заранее благодарю. https://www.cyberforum.ru/ c-cpp/ thread3109640.html	C/C++ Using namespace std https://www.cyberforum.ru/ c-cpp/ thread3109243.html Смысл писать кучу раз std:: если можно один раз using namespace std; :rofl::rofl::rofl::rofl::rofl::rofl:
С чего начать изучение С/С++ C/C++ С чего начать? :)	C/C++ Оптимальный счетчик элементов string выражения https://www.cyberforum.ru/ c-cpp/ thread3108531.html Добрый вечер. Есть выражение алгебры логики, записанное в string переменную. Мне нужно определить какие буквы использовал пользователь при вводе выражения, в нем может быть только A, B, C, X, Y, Z. Я выбрал простейший способ, а именно: if (expression.find('X') != -1) { for (int x = 0; x <= 1; x++) { variables = x;
C/C++ Сборка программы cmake https://www.cyberforum.ru/ c-cpp/ thread3108371.html Всем добрый день. Просьба немного помочь. Есть программа slang, хочу ее попробовать, по описанию - очень мне нужна. Но автор распространяет ее в виде исходников C++, бинарников не выкладывает. Нужно собрать под Windows 10. Есть вроде бы и инструкция по сборке Клонировал репозиторий. Установил MSYS2. Установил требуемые автором программы. $ gcc --version gcc (GCC) 11.3.0 Copyright (C)...	C/C++ Задача на теорию вероятностей Здравствуйте, помогите, пожалуйста, с решением задачи "Чёрные и белые". Рассмотрим игру. В ряд лежат n шариков двух цветов: черные и белые. Позиции в ряду пронумерованы от 1 до n. Вам известно только общее количество шариков (n); точное их расположение и даже количество белых шариков неизвестно. Вы можете делать запросы вида v u, где 1 ≤ v, u ≤ n. Если на позиции v находится чёрный шарик, а...
C/C++ Алиса и Боб (и снова тесты не проходят) После долгих мучений мне удалось достичь рабочего кода, но он выдаёт неверный ответ на шестом тесте. Ума не приложу, что должно быть в тесте, чтобы программа ошибалась. Задача: Ах, какая же скукота на летних каникулах! И вот, Алиса и Боб придумали новую игру. Правила у игры следующие: у игроков имеется множество из n различных целых чисел. Игроки ходят по очереди. Во время каждого хода... https://www.cyberforum.ru/ c-cpp/ thread3108128.html	C/C++ Задача про сапожника, не проходит тест https://www.cyberforum.ru/ c-cpp/ thread3107957.html В некоей воинской части есть сапожник. Рабочий день сапожника длится n минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано сапог, нуждающихся в починке. Определите, какое максимальное количество из них сапожник сможет починить за один рабочий день. Входные данные В первой строке...
C/C++ Ошибка при попытке статического анализа с компиляцией (плагин sonar-cxx) библиотеки GSL Запустил команду bear --use-cc - make Использовал файл sonar-project.properties с такими настройками: # must be unique in a given instance sonar.projectKey=gsl-with-build #sonar.language = cxx # Path is relative to the sonar-project.properties file. Defaults to . sonar.sources=. sonar.host.url=http://localhost:9000 # Encoding of the source code. Default is default system encoding	C/C++ Подскажите в чём моя ошибка Я работаю над заданием и никак не могу понять как правильно решать эту задачу Текст задачи: Турист, собираясь в поход, закупает продукты в неделимых упаковках известного веса Сj и калорийности aj, j=1..n. Количество продуктов каждого вида можно купить не более dj упаковок, j=1..n. Определить план закупки продуктов, чтобы их суммарная калорийность была не ниже К килокалорий, а общий вес был... https://www.cyberforum.ru/ c-cpp/ thread3107100.html

	09.06.2023, 12:43