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

@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

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

@alexu_007 · 07.06.2023, 13:15

1. Обычный цикл в любом случае быстрее рекурсии.
2. НОД меняется. Это видно на листинге работы программы. Для примера для чисел 9876543210 и 1234567890. НОД растёт 90 - 360 - 1080 - 11880 - 2150280. Последнее значение максимальное и его программа вычитает до нуля. При получении максимального значения НОД дальше можно не вычитать, результат вычисляется по формуле:

1232110440 / 2150280 + 37 = 610

Проблема только в том, как узнать что НОД максимальный и дальше расти не будет?

@gunslinger · 07.06.2023, 15:52

Что НОД может меняться, я даже и не предполагал (век живи, век учись).

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

Проблема только в том, как узнать что НОД максимальный и дальше расти не будет?

А вот это хороший вопрос (не зря, получается, слово "олимпиадная" в заголовке темы). Но идей пока нет.

Добавлено через 9 минут
Возможно, через какие-то свойства НОД?
Например,

Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b).

Только чем это поможет? Короче, надо думать (если получится).

Добавлено через 1 час 42 минуты
Еще есть предположение, что нужно не просто понять, когда НОД достиг максимума, но и в принципе определять ситуации с повторением НОД (до его возможного увеличения).
Вроде кажется, что разгадка близка, но пока ускользает.

данные

count = 0 ::::: gcd(9876543210, 1234567890) = 90 ::::: (x / gcd) and (y / gcd) = 109739369 and 13717421
count = 1 ::::: gcd(9876543120, 1234567800) = 360 ::::: (x / gcd) and (y / gcd) = 27434842 and 3429355
count = 2 ::::: gcd(9876542760, 1234567440) = 1080 ::::: (x / gcd) and (y / gcd) = 9144947 and 1143118
count = 3 ::::: gcd(9876541680, 1234566360) = 1080 ::::: (x / gcd) and (y / gcd) = 9144946 and 1143117
count = 4 ::::: gcd(9876540600, 1234565280) = 1080 ::::: (x / gcd) and (y / gcd) = 9144945 and 1143116
count = 5 ::::: gcd(9876539520, 1234564200) = 1080 ::::: (x / gcd) and (y / gcd) = 9144944 and 1143115
count = 6 ::::: gcd(9876538440, 1234563120) = 1080 ::::: (x / gcd) and (y / gcd) = 9144943 and 1143114
count = 7 ::::: gcd(9876537360, 1234562040) = 1080 ::::: (x / gcd) and (y / gcd) = 9144942 and 1143113
count = 8 ::::: gcd(9876536280, 1234560960) = 1080 ::::: (x / gcd) and (y / gcd) = 9144941 and 1143112
count = 9 ::::: gcd(9876535200, 1234559880) = 1080 ::::: (x / gcd) and (y / gcd) = 9144940 and 1143111
count = 10 ::::: gcd(9876534120, 1234558800) = 1080 ::::: (x / gcd) and (y / gcd) = 9144939 and 1143110
count = 11 ::::: gcd(9876533040, 1234557720) = 11880 ::::: (x / gcd) and (y / gcd) = 831358 and 103919
count = 12 ::::: gcd(9876521160, 1234545840) = 11880 ::::: (x / gcd) and (y / gcd) = 831357 and 103918
count = 13 ::::: gcd(9876509280, 1234533960) = 11880 ::::: (x / gcd) and (y / gcd) = 831356 and 103917
count = 14 ::::: gcd(9876497400, 1234522080) = 11880 ::::: (x / gcd) and (y / gcd) = 831355 and 103916
count = 15 ::::: gcd(9876485520, 1234510200) = 11880 ::::: (x / gcd) and (y / gcd) = 831354 and 103915
count = 16 ::::: gcd(9876473640, 1234498320) = 11880 ::::: (x / gcd) and (y / gcd) = 831353 and 103914
count = 17 ::::: gcd(9876461760, 1234486440) = 11880 ::::: (x / gcd) and (y / gcd) = 831352 and 103913
count = 18 ::::: gcd(9876449880, 1234474560) = 11880 ::::: (x / gcd) and (y / gcd) = 831351 and 103912
count = 19 ::::: gcd(9876438000, 1234462680) = 11880 ::::: (x / gcd) and (y / gcd) = 831350 and 103911
count = 20 ::::: gcd(9876426120, 1234450800) = 11880 ::::: (x / gcd) and (y / gcd) = 831349 and 103910
count = 21 ::::: gcd(9876414240, 1234438920) = 11880 ::::: (x / gcd) and (y / gcd) = 831348 and 103909
count = 22 ::::: gcd(9876402360, 1234427040) = 11880 ::::: (x / gcd) and (y / gcd) = 831347 and 103908
count = 23 ::::: gcd(9876390480, 1234415160) = 11880 ::::: (x / gcd) and (y / gcd) = 831346 and 103907
count = 24 ::::: gcd(9876378600, 1234403280) = 11880 ::::: (x / gcd) and (y / gcd) = 831345 and 103906
count = 25 ::::: gcd(9876366720, 1234391400) = 11880 ::::: (x / gcd) and (y / gcd) = 831344 and 103905
count = 26 ::::: gcd(9876354840, 1234379520) = 11880 ::::: (x / gcd) and (y / gcd) = 831343 and 103904
count = 27 ::::: gcd(9876342960, 1234367640) = 11880 ::::: (x / gcd) and (y / gcd) = 831342 and 103903
count = 28 ::::: gcd(9876331080, 1234355760) = 11880 ::::: (x / gcd) and (y / gcd) = 831341 and 103902
count = 29 ::::: gcd(9876319200, 1234343880) = 11880 ::::: (x / gcd) and (y / gcd) = 831340 and 103901
count = 30 ::::: gcd(9876307320, 1234332000) = 11880 ::::: (x / gcd) and (y / gcd) = 831339 and 103900
count = 31 ::::: gcd(9876295440, 1234320120) = 11880 ::::: (x / gcd) and (y / gcd) = 831338 and 103899
count = 32 ::::: gcd(9876283560, 1234308240) = 11880 ::::: (x / gcd) and (y / gcd) = 831337 and 103898
count = 33 ::::: gcd(9876271680, 1234296360) = 11880 ::::: (x / gcd) and (y / gcd) = 831336 and 103897
count = 34 ::::: gcd(9876259800, 1234284480) = 11880 ::::: (x / gcd) and (y / gcd) = 831335 and 103896
count = 35 ::::: gcd(9876247920, 1234272600) = 11880 ::::: (x / gcd) and (y / gcd) = 831334 and 103895
count = 36 ::::: gcd(9876236040, 1234260720) = 2150280 ::::: (x / gcd) and (y / gcd) = 4593 and 574
count = 37 ::::: gcd(9874085760, 1232110440) = 2150280 ::::: (x / gcd) and (y / gcd) = 4592 and 573
count = 38 ::::: gcd(9871935480, 1229960160) = 2150280 ::::: (x / gcd) and (y / gcd) = 4591 and 572
count = 39 ::::: gcd(9869785200, 1227809880) = 2150280 ::::: (x / gcd) and (y / gcd) = 4590 and 571
count = 40 ::::: gcd(9867634920, 1225659600) = 2150280 ::::: (x / gcd) and (y / gcd) = 4589 and 570
count = 41 ::::: gcd(9865484640, 1223509320) = 2150280 ::::: (x / gcd) and (y / gcd) = 4588 and 569
count = 42 ::::: gcd(9863334360, 1221359040) = 2150280 ::::: (x / gcd) and (y / gcd) = 4587 and 568
count = 43 ::::: gcd(9861184080, 1219208760) = 2150280 ::::: (x / gcd) and (y / gcd) = 4586 and 567
count = 44 ::::: gcd(9859033800, 1217058480) = 2150280 ::::: (x / gcd) and (y / gcd) = 4585 and 566
count = 45 ::::: gcd(9856883520, 1214908200) = 2150280 ::::: (x / gcd) and (y / gcd) = 4584 and 565
................................................................................ ...................................................................

данные с учетом вышеуказанного свойства НОД

count = 0 ::::: gcd(9876543210, 1234567890) = 90 ::::: (x / gcd) and (y / gcd) = 109739369 and 13717421
count = 1 ::::: gcd(109739368, 13717420) = 4 ::::: (x / gcd) and (y / gcd) = 27434842 and 3429355
count = 2 ::::: gcd(27434841, 3429354) = 3 ::::: (x / gcd) and (y / gcd) = 9144947 and 1143118
count = 3 ::::: gcd(9144946, 1143117) = 1 ::::: (x / gcd) and (y / gcd) = 9144946 and 1143117
count = 4 ::::: gcd(9144945, 1143116) = 1 ::::: (x / gcd) and (y / gcd) = 9144945 and 1143116
count = 5 ::::: gcd(9144944, 1143115) = 1 ::::: (x / gcd) and (y / gcd) = 9144944 and 1143115
count = 6 ::::: gcd(9144943, 1143114) = 1 ::::: (x / gcd) and (y / gcd) = 9144943 and 1143114
count = 7 ::::: gcd(9144942, 1143113) = 1 ::::: (x / gcd) and (y / gcd) = 9144942 and 1143113
count = 8 ::::: gcd(9144941, 1143112) = 1 ::::: (x / gcd) and (y / gcd) = 9144941 and 1143112
count = 9 ::::: gcd(9144940, 1143111) = 1 ::::: (x / gcd) and (y / gcd) = 9144940 and 1143111
count = 10 ::::: gcd(9144939, 1143110) = 1 ::::: (x / gcd) and (y / gcd) = 9144939 and 1143110
count = 11 ::::: gcd(9144938, 1143109) = 11 ::::: (x / gcd) and (y / gcd) = 831358 and 103919
count = 12 ::::: gcd(831357, 103918) = 1 ::::: (x / gcd) and (y / gcd) = 831357 and 103918
count = 13 ::::: gcd(831356, 103917) = 1 ::::: (x / gcd) and (y / gcd) = 831356 and 103917
count = 14 ::::: gcd(831355, 103916) = 1 ::::: (x / gcd) and (y / gcd) = 831355 and 103916
count = 15 ::::: gcd(831354, 103915) = 1 ::::: (x / gcd) and (y / gcd) = 831354 and 103915
count = 16 ::::: gcd(831353, 103914) = 1 ::::: (x / gcd) and (y / gcd) = 831353 and 103914
count = 17 ::::: gcd(831352, 103913) = 1 ::::: (x / gcd) and (y / gcd) = 831352 and 103913
count = 18 ::::: gcd(831351, 103912) = 1 ::::: (x / gcd) and (y / gcd) = 831351 and 103912
count = 19 ::::: gcd(831350, 103911) = 1 ::::: (x / gcd) and (y / gcd) = 831350 and 103911
count = 20 ::::: gcd(831349, 103910) = 1 ::::: (x / gcd) and (y / gcd) = 831349 and 103910
count = 21 ::::: gcd(831348, 103909) = 1 ::::: (x / gcd) and (y / gcd) = 831348 and 103909
count = 22 ::::: gcd(831347, 103908) = 1 ::::: (x / gcd) and (y / gcd) = 831347 and 103908
count = 23 ::::: gcd(831346, 103907) = 1 ::::: (x / gcd) and (y / gcd) = 831346 and 103907
count = 24 ::::: gcd(831345, 103906) = 1 ::::: (x / gcd) and (y / gcd) = 831345 and 103906
count = 25 ::::: gcd(831344, 103905) = 1 ::::: (x / gcd) and (y / gcd) = 831344 and 103905
count = 26 ::::: gcd(831343, 103904) = 1 ::::: (x / gcd) and (y / gcd) = 831343 and 103904
count = 27 ::::: gcd(831342, 103903) = 1 ::::: (x / gcd) and (y / gcd) = 831342 and 103903
count = 28 ::::: gcd(831341, 103902) = 1 ::::: (x / gcd) and (y / gcd) = 831341 and 103902
count = 29 ::::: gcd(831340, 103901) = 1 ::::: (x / gcd) and (y / gcd) = 831340 and 103901
count = 30 ::::: gcd(831339, 103900) = 1 ::::: (x / gcd) and (y / gcd) = 831339 and 103900
count = 31 ::::: gcd(831338, 103899) = 1 ::::: (x / gcd) and (y / gcd) = 831338 and 103899
count = 32 ::::: gcd(831337, 103898) = 1 ::::: (x / gcd) and (y / gcd) = 831337 and 103898
count = 33 ::::: gcd(831336, 103897) = 1 ::::: (x / gcd) and (y / gcd) = 831336 and 103897
count = 34 ::::: gcd(831335, 103896) = 1 ::::: (x / gcd) and (y / gcd) = 831335 and 103896
count = 35 ::::: gcd(831334, 103895) = 1 ::::: (x / gcd) and (y / gcd) = 831334 and 103895
count = 36 ::::: gcd(831333, 103894) = 181 ::::: (x / gcd) and (y / gcd) = 4593 and 574
count = 37 ::::: gcd(4592, 573) = 1 ::::: (x / gcd) and (y / gcd) = 4592 and 573
count = 38 ::::: gcd(4591, 572) = 1 ::::: (x / gcd) and (y / gcd) = 4591 and 572
count = 39 ::::: gcd(4590, 571) = 1 ::::: (x / gcd) and (y / gcd) = 4590 and 571
count = 40 ::::: gcd(4589, 570) = 1 ::::: (x / gcd) and (y / gcd) = 4589 and 570
count = 41 ::::: gcd(4588, 569) = 1 ::::: (x / gcd) and (y / gcd) = 4588 and 569
count = 42 ::::: gcd(4587, 568) = 1 ::::: (x / gcd) and (y / gcd) = 4587 and 568
count = 43 ::::: gcd(4586, 567) = 1 ::::: (x / gcd) and (y / gcd) = 4586 and 567
count = 44 ::::: gcd(4585, 566) = 1 ::::: (x / gcd) and (y / gcd) = 4585 and 566
count = 45 ::::: gcd(4584, 565) = 1 ::::: (x / gcd) and (y / gcd) = 4584 and 565
................................................................................ ...................................................................

@gunslinger · 07.06.2023, 19:03

Нашел такое свойство:

Может его как-то получится использовать? У меня идей больше нет.

@gunslinger · 08.06.2023, 04:14

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

Проблема только в том, как узнать что НОД максимальный и дальше расти не будет?

Я, кажется, понял. После каждого нахождения НОД делим x и y на НОД, получая новые значения x и y.
Если НОД = 1 (в какой-то момент), то далее вычисляем |x - y|. Если эта разница равна 1 или является простым числом, то к счетчику операций добавляем минимальное из двух чисел x и y. Это и будет ответ. Код ниже.

C++

typedef unsigned long long ull;
//---------------------------------------------------------------------------
ull gcd (ull a, ull b)
{
  return a ? gcd(b % a, a) : b;
}
//---------------------------------------------------------------------------
bool is_prime (ull n)
{
  if (n < 2)
    return 0;
  if (n == 2)
    return 1;
  if (!(n % 2))
    return 0;
  for (int j = 3; j * j <= n; j += 2)
    if (!(n % j))
      return 0;
  return 1;
}
//---------------------------------------------------------------------------
ull func (ull x, ull y)
{
  ull num, count = 0;
  do
  {
    num = gcd(x, y);
    x /= num, y /= num;
    if (num == 1)
    {
      ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min;
      if (dif == 1 || is_prime(dif))
        return count + min;
    }
    x--, y--, count++;
  } 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
total count = 729582

count = 0 ::::: gcd(9876543210, 1234567890) = 90 ::::: (x / gcd) and (y / gcd) = 109739369 and 13717421
count = 1 ::::: gcd(109739368, 13717420) = 4 ::::: (x / gcd) and (y / gcd) = 27434842 and 3429355
count = 2 ::::: gcd(27434841, 3429354) = 3 ::::: (x / gcd) and (y / gcd) = 9144947 and 1143118
count = 3 ::::: gcd(9144946, 1143117) = 1 ::::: (x / gcd) and (y / gcd) = 9144946 and 1143117
count = 4 ::::: gcd(9144945, 1143116) = 1 ::::: (x / gcd) and (y / gcd) = 9144945 and 1143116
count = 5 ::::: gcd(9144944, 1143115) = 1 ::::: (x / gcd) and (y / gcd) = 9144944 and 1143115
count = 6 ::::: gcd(9144943, 1143114) = 1 ::::: (x / gcd) and (y / gcd) = 9144943 and 1143114
count = 7 ::::: gcd(9144942, 1143113) = 1 ::::: (x / gcd) and (y / gcd) = 9144942 and 1143113
count = 8 ::::: gcd(9144941, 1143112) = 1 ::::: (x / gcd) and (y / gcd) = 9144941 and 1143112
count = 9 ::::: gcd(9144940, 1143111) = 1 ::::: (x / gcd) and (y / gcd) = 9144940 and 1143111
count = 10 ::::: gcd(9144939, 1143110) = 1 ::::: (x / gcd) and (y / gcd) = 9144939 and 1143110
count = 11 ::::: gcd(9144938, 1143109) = 11 ::::: (x / gcd) and (y / gcd) = 831358 and 103919
count = 12 ::::: gcd(831357, 103918) = 1 ::::: (x / gcd) and (y / gcd) = 831357 and 103918
count = 13 ::::: gcd(831356, 103917) = 1 ::::: (x / gcd) and (y / gcd) = 831356 and 103917
count = 14 ::::: gcd(831355, 103916) = 1 ::::: (x / gcd) and (y / gcd) = 831355 and 103916
count = 15 ::::: gcd(831354, 103915) = 1 ::::: (x / gcd) and (y / gcd) = 831354 and 103915
count = 16 ::::: gcd(831353, 103914) = 1 ::::: (x / gcd) and (y / gcd) = 831353 and 103914
count = 17 ::::: gcd(831352, 103913) = 1 ::::: (x / gcd) and (y / gcd) = 831352 and 103913
count = 18 ::::: gcd(831351, 103912) = 1 ::::: (x / gcd) and (y / gcd) = 831351 and 103912
count = 19 ::::: gcd(831350, 103911) = 1 ::::: (x / gcd) and (y / gcd) = 831350 and 103911
count = 20 ::::: gcd(831349, 103910) = 1 ::::: (x / gcd) and (y / gcd) = 831349 and 103910
count = 21 ::::: gcd(831348, 103909) = 1 ::::: (x / gcd) and (y / gcd) = 831348 and 103909
count = 22 ::::: gcd(831347, 103908) = 1 ::::: (x / gcd) and (y / gcd) = 831347 and 103908
count = 23 ::::: gcd(831346, 103907) = 1 ::::: (x / gcd) and (y / gcd) = 831346 and 103907
count = 24 ::::: gcd(831345, 103906) = 1 ::::: (x / gcd) and (y / gcd) = 831345 and 103906
count = 25 ::::: gcd(831344, 103905) = 1 ::::: (x / gcd) and (y / gcd) = 831344 and 103905
count = 26 ::::: gcd(831343, 103904) = 1 ::::: (x / gcd) and (y / gcd) = 831343 and 103904
count = 27 ::::: gcd(831342, 103903) = 1 ::::: (x / gcd) and (y / gcd) = 831342 and 103903
count = 28 ::::: gcd(831341, 103902) = 1 ::::: (x / gcd) and (y / gcd) = 831341 and 103902
count = 29 ::::: gcd(831340, 103901) = 1 ::::: (x / gcd) and (y / gcd) = 831340 and 103901
count = 30 ::::: gcd(831339, 103900) = 1 ::::: (x / gcd) and (y / gcd) = 831339 and 103900
count = 31 ::::: gcd(831338, 103899) = 1 ::::: (x / gcd) and (y / gcd) = 831338 and 103899
count = 32 ::::: gcd(831337, 103898) = 1 ::::: (x / gcd) and (y / gcd) = 831337 and 103898
count = 33 ::::: gcd(831336, 103897) = 1 ::::: (x / gcd) and (y / gcd) = 831336 and 103897
count = 34 ::::: gcd(831335, 103896) = 1 ::::: (x / gcd) and (y / gcd) = 831335 and 103896
count = 35 ::::: gcd(831334, 103895) = 1 ::::: (x / gcd) and (y / gcd) = 831334 and 103895
count = 36 ::::: gcd(831333, 103894) = 181 ::::: (x / gcd) and (y / gcd) = 4593 and 574
count = 37 ::::: gcd(4592, 573) = 1 ::::: (x / gcd) and (y / gcd) = 4592 and 573
total count = 610

count = 0 ::::: gcd(127476953, 384634629) = 1 ::::: (x / gcd) and (y / gcd) = 127476953 and 384634629
count = 1 ::::: gcd(127476952, 384634628) = 4 ::::: (x / gcd) and (y / gcd) = 31869238 and 96158657
count = 2 ::::: gcd(31869237, 96158656) = 1 ::::: (x / gcd) and (y / gcd) = 31869237 and 96158656
count = 3 ::::: gcd(31869236, 96158655) = 1 ::::: (x / gcd) and (y / gcd) = 31869236 and 96158655
count = 4 ::::: gcd(31869235, 96158654) = 1 ::::: (x / gcd) and (y / gcd) = 31869235 and 96158654
count = 5 ::::: gcd(31869234, 96158653) = 1 ::::: (x / gcd) and (y / gcd) = 31869234 and 96158653
count = 6 ::::: gcd(31869233, 96158652) = 1 ::::: (x / gcd) and (y / gcd) = 31869233 and 96158652
count = 7 ::::: gcd(31869232, 96158651) = 1 ::::: (x / gcd) and (y / gcd) = 31869232 and 96158651
count = 8 ::::: gcd(31869231, 96158650) = 1 ::::: (x / gcd) and (y / gcd) = 31869231 and 96158650
count = 9 ::::: gcd(31869230, 96158649) = 1 ::::: (x / gcd) and (y / gcd) = 31869230 and 96158649
count = 10 ::::: gcd(31869229, 96158648) = 1 ::::: (x / gcd) and (y / gcd) = 31869229 and 96158648
count = 11 ::::: gcd(31869228, 96158647) = 1 ::::: (x / gcd) and (y / gcd) = 31869228 and 96158647
count = 12 ::::: gcd(31869227, 96158646) = 1 ::::: (x / gcd) and (y / gcd) = 31869227 and 96158646
count = 13 ::::: gcd(31869226, 96158645) = 1 ::::: (x / gcd) and (y / gcd) = 31869226 and 96158645
count = 14 ::::: gcd(31869225, 96158644) = 1 ::::: (x / gcd) and (y / gcd) = 31869225 and 96158644
count = 15 ::::: gcd(31869224, 96158643) = 1 ::::: (x / gcd) and (y / gcd) = 31869224 and 96158643
count = 16 ::::: gcd(31869223, 96158642) = 1 ::::: (x / gcd) and (y / gcd) = 31869223 and 96158642
count = 17 ::::: gcd(31869222, 96158641) = 1 ::::: (x / gcd) and (y / gcd) = 31869222 and 96158641
count = 18 ::::: gcd(31869221, 96158640) = 1 ::::: (x / gcd) and (y / gcd) = 31869221 and 96158640
count = 19 ::::: gcd(31869220, 96158639) = 1 ::::: (x / gcd) and (y / gcd) = 31869220 and 96158639
count = 20 ::::: gcd(31869219, 96158638) = 1 ::::: (x / gcd) and (y / gcd) = 31869219 and 96158638
count = 21 ::::: gcd(31869218, 96158637) = 1 ::::: (x / gcd) and (y / gcd) = 31869218 and 96158637
count = 22 ::::: gcd(31869217, 96158636) = 1 ::::: (x / gcd) and (y / gcd) = 31869217 and 96158636
count = 23 ::::: gcd(31869216, 96158635) = 1 ::::: (x / gcd) and (y / gcd) = 31869216 and 96158635
count = 24 ::::: gcd(31869215, 96158634) = 1 ::::: (x / gcd) and (y / gcd) = 31869215 and 96158634
count = 25 ::::: gcd(31869214, 96158633) = 1 ::::: (x / gcd) and (y / gcd) = 31869214 and 96158633
count = 26 ::::: gcd(31869213, 96158632) = 1 ::::: (x / gcd) and (y / gcd) = 31869213 and 96158632
count = 27 ::::: gcd(31869212, 96158631) = 1 ::::: (x / gcd) and (y / gcd) = 31869212 and 96158631
count = 28 ::::: gcd(31869211, 96158630) = 1 ::::: (x / gcd) and (y / gcd) = 31869211 and 96158630
count = 29 ::::: gcd(31869210, 96158629) = 1 ::::: (x / gcd) and (y / gcd) = 31869210 and 96158629
count = 30 ::::: gcd(31869209, 96158628) = 1 ::::: (x / gcd) and (y / gcd) = 31869209 and 96158628
count = 31 ::::: gcd(31869208, 96158627) = 1 ::::: (x / gcd) and (y / gcd) = 31869208 and 96158627
count = 32 ::::: gcd(31869207, 96158626) = 1 ::::: (x / gcd) and (y / gcd) = 31869207 and 96158626
count = 33 ::::: gcd(31869206, 96158625) = 1 ::::: (x / gcd) and (y / gcd) = 31869206 and 96158625
count = 34 ::::: gcd(31869205, 96158624) = 1 ::::: (x / gcd) and (y / gcd) = 31869205 and 96158624
count = 35 ::::: gcd(31869204, 96158623) = 1 ::::: (x / gcd) and (y / gcd) = 31869204 and 96158623
count = 36 ::::: gcd(31869203, 96158622) = 1 ::::: (x / gcd) and (y / gcd) = 31869203 and 96158622
count = 37 ::::: gcd(31869202, 96158621) = 1 ::::: (x / gcd) and (y / gcd) = 31869202 and 96158621
count = 38 ::::: gcd(31869201, 96158620) = 1 ::::: (x / gcd) and (y / gcd) = 31869201 and 96158620
count = 39 ::::: gcd(31869200, 96158619) = 1 ::::: (x / gcd) and (y / gcd) = 31869200 and 96158619
count = 40 ::::: gcd(31869199, 96158618) = 1 ::::: (x / gcd) and (y / gcd) = 31869199 and 96158618
count = 41 ::::: gcd(31869198, 96158617) = 1 ::::: (x / gcd) and (y / gcd) = 31869198 and 96158617
count = 42 ::::: gcd(31869197, 96158616) = 1 ::::: (x / gcd) and (y / gcd) = 31869197 and 96158616
count = 43 ::::: gcd(31869196, 96158615) = 1 ::::: (x / gcd) and (y / gcd) = 31869196 and 96158615
count = 44 ::::: gcd(31869195, 96158614) = 1 ::::: (x / gcd) and (y / gcd) = 31869195 and 96158614
count = 45 ::::: gcd(31869194, 96158613) = 1 ::::: (x / gcd) and (y / gcd) = 31869194 and 96158613
count = 46 ::::: gcd(31869193, 96158612) = 353 ::::: (x / gcd) and (y / gcd) = 90281 and 272404
count = 47 ::::: gcd(90280, 272403) = 1 ::::: (x / gcd) and (y / gcd) = 90280 and 272403
total count = 90327

count = 0 ::::: gcd(636639704, 305783529) = 1 ::::: (x / gcd) and (y / gcd) = 636639704 and 305783529
count = 1 ::::: gcd(636639703, 305783528) = 1 ::::: (x / gcd) and (y / gcd) = 636639703 and 305783528
count = 2 ::::: gcd(636639702, 305783527) = 1 ::::: (x / gcd) and (y / gcd) = 636639702 and 305783527
count = 3 ::::: gcd(636639701, 305783526) = 1 ::::: (x / gcd) and (y / gcd) = 636639701 and 305783526
count = 4 ::::: gcd(636639700, 305783525) = 25 ::::: (x / gcd) and (y / gcd) = 25465588 and 12231341
count = 5 ::::: gcd(25465587, 12231340) = 1 ::::: (x / gcd) and (y / gcd) = 25465587 and 12231340
count = 6 ::::: gcd(25465586, 12231339) = 1 ::::: (x / gcd) and (y / gcd) = 25465586 and 12231339
count = 7 ::::: gcd(25465585, 12231338) = 1 ::::: (x / gcd) and (y / gcd) = 25465585 and 12231338
count = 8 ::::: gcd(25465584, 12231337) = 1 ::::: (x / gcd) and (y / gcd) = 25465584 and 12231337
count = 9 ::::: gcd(25465583, 12231336) = 13 ::::: (x / gcd) and (y / gcd) = 1958891 and 940872
count = 10 ::::: gcd(1958890, 940871) = 1 ::::: (x / gcd) and (y / gcd) = 1958890 and 940871
total count = 940881

Добавлено через 1 час 20 минут
Можно еще дополнительную оптимизацию сделать.
Если НОД "первый раз" стал равен 1, то мы делаем проверку выражения |x - y|, как указано выше.
Если далее НОД снова равен 1, то проверку не делаем до тех пор, пока НОД не примет значение > 1 и потом снова "первый раз" станет равен 1 (и так далее, процесс повторяем).

Измененная функция:

C++

ull func (ull x, ull y)
{
  ull num, count = 0;
  bool num_was_one = 0;
  do
  {
    num = gcd(x, y);
    x /= num, y /= num;
    if (num == 1 && !num_was_one)
    {
      ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min;
      if (dif == 1 || is_prime(dif))
        return count + min;
    }
    x--, y--, count++;
    num_was_one = (num == 1);
  } while(x > 0 && y > 0);
  return count;
}

@alexu_007 · 08.06.2023, 16:51

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
total count = 729582

В этом тесте у меня получился другой результат:

@gunslinger · 08.06.2023, 19:20

Если я правильно понял, ты вычитаешь НОД из x и y, а нужно делить x и y на НОД. Верно?

@alexu_007 · 08.06.2023, 19:35

Так вроде в задании?

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

@gunslinger · 08.06.2023, 21:12

Это понятно. Я просто почему-то подумал, что ты используешь решение через сокращение x и y на НОД с дальнейшим декрементом x и y (полагал, что так проще).

C++

    num = gcd(x, y);
    x /= num, y /= num;
    //.................................
    x--, y--, count++;

Возможно, я перемудрил и мой способ не верен. Нужно посмотреть получше либо стОит строго следовать алгоритму задачи.
В любом случае хотелось бы иметь возможность протестировать код там, где это делает Tonendd. Чтобы была нормальная обратная связь вида "код -> решение", а не гадание и домыслы (с моей стороны).

Добавлено через 23 минуты
alexu_007, у тебя в последнем примере на первом шаге стоит 0(-ой шаг). Должно быть вроде 1 и так далее или нет?
У меня нулевой шаг - начальные данные.
Но это мелочи. Если не секрет, как у тебя последняя строка в примере формируется?
Число шагов откуда берется и почему такое? Второе число, как я понял, разница между x и y (верно?). Третье число - двойное предыдущее число (почему?). Четвертое = второму (почему?).
Получается, что на твоем шаге №3 или №4 (предпоследняя строка) НОД уже не меняется? У меня это шаг №4.

Добавлено через 41 минуту
Переделал под "точный алгоритм задачи" - суть не изменилась. Значит, моя идея (с сокращением x и y на НОД) по сути была верна. Тогда выходит, что я изначально чего-то не так делаю или "ничего не понимаю".

C++

ull func (ull x, ull y)
{
  ull num, num2 = 0, count = 0;
  bool same_prev_num = 0;
  do
  {
    num = gcd(x, y);
    same_prev_num = (num2 == num);
    if (same_prev_num)
    {
      ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min;
      if (dif == 1 || is_prime(dif / num))
        return count + min / num;
    }
    x -= num, y -= num, count++;
    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(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 = 4 ::::: gcd(408563680, 584375120) = 560 ::::: (x / gcd) and (y / gcd) = 729578 and 1043527
---------------------------------------------------------------------------
total count = 729582 (x = 408564263, y = 584375703)

@alexu_007 · 09.06.2023, 06:54

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

Если не секрет, как у тебя последняя строка в примере формируется?

Если скан из поста 25, то там выводятся только те строки, где меняется НОД. Изначальный НОД = 0, поэтому в первом действии он меняется на 1 и выводится на экран в виде: счётчик - НОД - (X-НОД) - (Y-НОД). Далее, X и Y после вычитания единицы становятся чётными - НОД становится равным 2. После вычитания 2 НОД становится равным 20, и снова вывод на экран. После вычитания 20 НОД становится равным 560 и остаётся таким в течение 101681 шагов - столько раз из X и Y вычитается 560. И на последнем шаге НОД становится равным 17581440.

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

@gunslinger · 09.06.2023, 12:58

Еще пара результатов:

count = 0 ::::: gcd(375412775, 66439544) = 1 ::::: (x / gcd) and (y / gcd) = 375412775 and 66439544
count = 1 ::::: gcd(375412774, 66439543) = 1 ::::: (x / gcd) and (y / gcd) = 375412774 and 66439543
count = 2 ::::: gcd(375412773, 66439542) = 57 ::::: (x / gcd) and (y / gcd) = 6586189 and 1165606
count = 3 ::::: gcd(6586188, 1165605) = 21 ::::: (x / gcd) and (y / gcd) = 313628 and 55505
count = 4 ::::: gcd(313627, 55504) = 1 ::::: (x / gcd) and (y / gcd) = 313627 and 55504
count = 5 ::::: gcd(313626, 55503) = 3 ::::: (x / gcd) and (y / gcd) = 104542 and 18501
count = 6 ::::: gcd(104541, 18500) = 1 ::::: (x / gcd) and (y / gcd) = 104541 and 18500
count = 7 ::::: gcd(104540, 18499) = 1 ::::: (x / gcd) and (y / gcd) = 104540 and 18499
count = 8 ::::: gcd(104539, 18498) = 1 ::::: (x / gcd) and (y / gcd) = 104539 and 18498
count = 9 ::::: gcd(104538, 18497) = 1 ::::: (x / gcd) and (y / gcd) = 104538 and 18497
count = 10 ::::: gcd(104537, 18496) = 1 ::::: (x / gcd) and (y / gcd) = 104537 and 18496
count = 11 ::::: gcd(104536, 18495) = 1 ::::: (x / gcd) and (y / gcd) = 104536 and 18495
count = 12 ::::: gcd(104535, 18494) = 1 ::::: (x / gcd) and (y / gcd) = 104535 and 18494
count = 13 ::::: gcd(104534, 18493) = 1 ::::: (x / gcd) and (y / gcd) = 104534 and 18493
count = 14 ::::: gcd(104533, 18492) = 1 ::::: (x / gcd) and (y / gcd) = 104533 and 18492
count = 15 ::::: gcd(104532, 18491) = 1 ::::: (x / gcd) and (y / gcd) = 104532 and 18491
count = 16 ::::: gcd(104531, 18490) = 1 ::::: (x / gcd) and (y / gcd) = 104531 and 18490
count = 17 ::::: gcd(104530, 18489) = 1 ::::: (x / gcd) and (y / gcd) = 104530 and 18489
count = 18 ::::: gcd(104529, 18488) = 1 ::::: (x / gcd) and (y / gcd) = 104529 and 18488
count = 19 ::::: gcd(104528, 18487) = 139 ::::: (x / gcd) and (y / gcd) = 752 and 133
count = 20 ::::: gcd(751, 132) = 1 ::::: (x / gcd) and (y / gcd) = 751 and 132
---------------------------------------------------------------------------
total count = 152 (x = 375412775, y = 66439544)

и

@gunslinger · 09.06.2023, 13:10

И просто результаты (без промежуточных):

здесь

---------------------------------------------------------------------------
total count = 289392621 (x = 587262902808, y = 492038517893)
---------------------------------------------------------------------------
total count = 143771 (x = 287015498828, y = 67150419662)
---------------------------------------------------------------------------
total count = 713 (x = 646979228480, y = 518778413168)
---------------------------------------------------------------------------
total count = 585341772 (x = 749797493833, y = 635172282207)
---------------------------------------------------------------------------
total count = 1991 (x = 572319499792, y = 19911540797)
---------------------------------------------------------------------------
total count = 1078 (x = 164377035096, y = 273251396566)
---------------------------------------------------------------------------
total count = 10537584064 (x = 466061396841, y = 179138928880)
---------------------------------------------------------------------------
total count = 721 (x = 94107627788, y = 28054485835)
---------------------------------------------------------------------------
total count = 55669 (x = 9919083945, y = 423306399416)
---------------------------------------------------------------------------
total count = 229222912 (x = 321689360014, y = 339369972049)
---------------------------------------------------------------------------
total count = 100796 (x = 392730946459, y = 707581506287)
---------------------------------------------------------------------------
total count = 320498 (x = 571153090401, y = 209569804234)
---------------------------------------------------------------------------
total count = 2149564 (x = 338618687020, y = 719572825094)
---------------------------------------------------------------------------
total count = 58955 (x = 691092716312, y = 352748197861)
---------------------------------------------------------------------------
total count = 3244864099 (x = 906119866525, y = 919498751218)
---------------------------------------------------------------------------
total count = 26998 (x = 879838649620, y = 175526662956)
---------------------------------------------------------------------------
total count = 1703554724 (x = 551222582101, y = 567034174589)
---------------------------------------------------------------------------
total count = 3934510213 (x = 423074349212, y = 165249428726)
---------------------------------------------------------------------------
total count = 113709 (x = 579033458118, y = 110429234643)
---------------------------------------------------------------------------
total count = 718692395 (x = 191774955469, y = 301618979107)
---------------------------------------------------------------------------
total count = 5599201 (x = 127219094035, y = 621181734324)
---------------------------------------------------------------------------
total count = 11682 (x = 475651367997, y = 436167100858)
---------------------------------------------------------------------------
total count = 2244328 (x = 4946408163, y = 646361318359)
---------------------------------------------------------------------------
total count = 771475 (x = 590039835676, y = 647825558860)
---------------------------------------------------------------------------
total count = 3052 (x = 887773574097, y = 598926375986)
---------------------------------------------------------------------------
total count = 89892559 (x = 757594518430, y = 688262383415)
---------------------------------------------------------------------------
total count = 11225799558 (x = 293509512362, y = 497212628274)
---------------------------------------------------------------------------
total count = 262602 (x = 513869571781, y = 173376299691)
---------------------------------------------------------------------------
total count = 70595329 (x = 680999990876, y = 128692559055)
---------------------------------------------------------------------------
total count = 14797 (x = 881196520325, y = 636157037313)
---------------------------------------------------------------------------
total count = 72995 (x = 549041999823, y = 339580196233)
---------------------------------------------------------------------------
total count = 961980084 (x = 554159688046, y = 536780074910)
---------------------------------------------------------------------------
total count = 2093146 (x = 541798617045, y = 251929924106)
---------------------------------------------------------------------------
total count = 935 (x = 440813457676, y = 11656084126)
---------------------------------------------------------------------------
total count = 81044900 (x = 877979232154, y = 765381875550)
---------------------------------------------------------------------------
total count = 187587032 (x = 468855189980, y = 694091020674)
---------------------------------------------------------------------------
total count = 16273372374 (x = 387761843519, y = 612789963349)
---------------------------------------------------------------------------
total count = 7200485 (x = 634686980392, y = 470452733803)
---------------------------------------------------------------------------
total count = 20358339326 (x = 614137431969, y = 778133230647)
---------------------------------------------------------------------------
total count = 481276824 (x = 859225656513, y = 276734163788)
---------------------------------------------------------------------------
total count = 110865980267 (x = 743238192539, y = 221731960533)
---------------------------------------------------------------------------
total count = 172093550 (x = 165381881990, y = 508143834477)
---------------------------------------------------------------------------
total count = 6542 (x = 825552629073, y = 154245038261)
---------------------------------------------------------------------------
total count = 36196768 (x = 419890140771, y = 153437838360)
---------------------------------------------------------------------------
total count = 41931 (x = 18289025113, y = 751830268751)
---------------------------------------------------------------------------
total count = 6263807 (x = 377335001592, y = 148707944795)
---------------------------------------------------------------------------
total count = 43518069 (x = 300962899779, y = 558320767137)
---------------------------------------------------------------------------
total count = 803618 (x = 478138641621, y = 15670382121)
---------------------------------------------------------------------------
total count = 1855922926 (x = 128058681758, y = 410616851411)
---------------------------------------------------------------------------
total count = 2435918 (x = 334895797368, y = 958896765396)
---------------------------------------------------------------------------
total count = 1718070 (x = 464028889331, y = 872254772205)
---------------------------------------------------------------------------
total count = 11811302889 (x = 818233985858, y = 366150389469)
---------------------------------------------------------------------------
total count = 13627403288 (x = 136274032864, y = 625507535574)
---------------------------------------------------------------------------
total count = 386027 (x = 99017586433, y = 793034991893)
---------------------------------------------------------------------------
total count = 38214983285 (x = 603077898881, y = 938650914792)
---------------------------------------------------------------------------
total count = 9053455409 (x = 699338213138, y = 226336385113)
---------------------------------------------------------------------------
total count = 8481422 (x = 841675973844, y = 750534932032)
---------------------------------------------------------------------------
total count = 6680776 (x = 268157994358, y = 861698966679)
---------------------------------------------------------------------------
total count = 14992896 (x = 332155382601, y = 191614135270)
---------------------------------------------------------------------------
total count = 1221 (x = 15888631833, y = 644300786344)
---------------------------------------------------------------------------
total count = 6391 (x = 579917831532, y = 794607208300)
---------------------------------------------------------------------------
total count = 619253 (x = 102211515045, y = 784166400364)
---------------------------------------------------------------------------
total count = 30388 (x = 902950907599, y = 187894926748)
---------------------------------------------------------------------------
total count = 1496796560 (x = 374593268390, y = 598010089221)
---------------------------------------------------------------------------
total count = 2926 (x = 127637685937, y = 135150988833)
---------------------------------------------------------------------------
total count = 22339864 (x = 867507014999, y = 354197251844)
---------------------------------------------------------------------------
total count = 132906267 (x = 679481242303, y = 762356351027)
---------------------------------------------------------------------------
total count = 38254 (x = 208042128539, y = 773093253611)
---------------------------------------------------------------------------
total count = 8557491 (x = 781684205740, y = 137133754815)
---------------------------------------------------------------------------
total count = 1024 (x = 774068162490, y = 582953978160)
---------------------------------------------------------------------------
total count = 1354 (x = 336759532033, y = 325141309962)
---------------------------------------------------------------------------
total count = 390673600 (x = 682809794851, y = 736910783813)
---------------------------------------------------------------------------
total count = 34908 (x = 402512726754, y = 703066415189)
---------------------------------------------------------------------------
total count = 1983280 (x = 626406297431, y = 8267504280)
---------------------------------------------------------------------------
total count = 21502995694 (x = 258035948322, y = 958854899694)
---------------------------------------------------------------------------
total count = 2561672498 (x = 122960279793, y = 978282809889)
---------------------------------------------------------------------------
total count = 60474 (x = 239987302569, y = 131654462846)
---------------------------------------------------------------------------
total count = 18469 (x = 258899716328, y = 166253928733)
---------------------------------------------------------------------------
total count = 1041113219 (x = 482786205773, y = 70795698057)
---------------------------------------------------------------------------
total count = 4512498 (x = 600468561566, y = 296420184464)
---------------------------------------------------------------------------
total count = 45881 (x = 750865388044, y = 425047896863)
---------------------------------------------------------------------------
total count = 47980961 (x = 618727119156, y = 141543742006)
---------------------------------------------------------------------------
total count = 7190642906 (x = 891681047646, y = 995051705343)
---------------------------------------------------------------------------
total count = 4106403546 (x = 53383246098, y = 370961899321)
---------------------------------------------------------------------------
total count = 29365523405 (x = 728603320068, y = 452398230246)
---------------------------------------------------------------------------
total count = 33436292 (x = 556708396554, y = 337904172292)
---------------------------------------------------------------------------
total count = 124712551764 (x = 713804216389, y = 566531300232)
---------------------------------------------------------------------------
total count = 345740 (x = 304226729354, y = 471803880807)
---------------------------------------------------------------------------
total count = 26901 (x = 306067029128, y = 9829445431)
---------------------------------------------------------------------------
total count = 3161400 (x = 622949606347, y = 818313709455)
---------------------------------------------------------------------------
total count = 35653 (x = 56854629180, y = 543546826352)
---------------------------------------------------------------------------
total count = 3558 (x = 882421427558, y = 40733054084)
---------------------------------------------------------------------------
total count = 4864768 (x = 347683698096, y = 795513366862)
---------------------------------------------------------------------------
total count = 5566 (x = 965404079623, y = 484609489026)
---------------------------------------------------------------------------
total count = 4782298 (x = 470429915800, y = 891033182749)
---------------------------------------------------------------------------
total count = 486096450 (x = 893386402585, y = 668667431306)
---------------------------------------------------------------------------
total count = 30140 (x = 108348032230, y = 988051331607)
---------------------------------------------------------------------------
total count = 336992 (x = 370584258356, y = 869601546514)
---------------------------------------------------------------------------
total count = 676893295 (x = 767822818466, y = 807878286136)
---------------------------------------------------------------------------
total count = 6209321 (x = 573257715681, y = 894555117287)
---------------------------------------------------------------------------
total count = 287733128310 (x = 756082618549, y = 287733128310)
---------------------------------------------------------------------------
total count = 24085898 (x = 704781787827, y = 333950619172)
---------------------------------------------------------------------------
total count = 3107 (x = 888835818961, y = 977323644180)
---------------------------------------------------------------------------
total count = 599653 (x = 727531921689, y = 824239376988)
---------------------------------------------------------------------------
total count = 6823926 (x = 50469368613, y = 441169880329)
---------------------------------------------------------------------------
total count = 13462 (x = 350051341159, y = 373609236377)
---------------------------------------------------------------------------
total count = 378290224648 (x = 764398512077, y = 378290224648)
---------------------------------------------------------------------------
total count = 21709 (x = 366943536802, y = 758675238020)
---------------------------------------------------------------------------
total count = 815041 (x = 380835953899, y = 429179115414)
---------------------------------------------------------------------------
total count = 11030490075 (x = 955781112108, y = 845960151901)
---------------------------------------------------------------------------
total count = 4328 (x = 38140736528, y = 755060072441)
---------------------------------------------------------------------------
total count = 2469 (x = 807558470227, y = 731643464219)
---------------------------------------------------------------------------
total count = 225372168627 (x = 225372168627, y = 559815630326)
---------------------------------------------------------------------------
total count = 762030 (x = 822329420114, y = 486228115482)
---------------------------------------------------------------------------
total count = 561486 (x = 200651904274, y = 353477137501)
---------------------------------------------------------------------------
total count = 165926 (x = 320293645265, y = 798398759917)
---------------------------------------------------------------------------
total count = 4651796 (x = 730123420600, y = 891911208682)
---------------------------------------------------------------------------
total count = 30379 (x = 40440306937, y = 771830167344)
---------------------------------------------------------------------------
total count = 480534 (x = 522775283919, y = 556960287339)
---------------------------------------------------------------------------
total count = 626141 (x = 140002415590, y = 579917807942)
---------------------------------------------------------------------------
total count = 991 (x = 620143263344, y = 81580643441)
---------------------------------------------------------------------------
total count = 23502247 (x = 757641184699, y = 455691334545)
---------------------------------------------------------------------------
total count = 47261944806 (x = 283571668828, y = 824195091274)
---------------------------------------------------------------------------
total count = 4119864751 (x = 594308034301, y = 708225803467)
---------------------------------------------------------------------------
total count = 27307 (x = 781184153168, y = 92880993282)
---------------------------------------------------------------------------
total count = 10701150 (x = 291942046441, y = 114956838750)
---------------------------------------------------------------------------
total count = 116277 (x = 441856324889, y = 696672463014)
---------------------------------------------------------------------------
total count = 29465007 (x = 913140697511, y = 182682904911)
---------------------------------------------------------------------------
total count = 57499 (x = 906157878563, y = 757852253705)
---------------------------------------------------------------------------
total count = 4959291 (x = 859869238623, y = 270941123503)
---------------------------------------------------------------------------
total count = 1020 (x = 115312341096, y = 145729360712)
---------------------------------------------------------------------------
total count = 127673 (x = 327430210427, y = 168156797525)
---------------------------------------------------------------------------
total count = 17998715384 (x = 35997430768, y = 931355554574)
---------------------------------------------------------------------------
total count = 1803 (x = 940030890476, y = 364022344534)
---------------------------------------------------------------------------
total count = 58143 (x = 135617435019, y = 854147794771)
---------------------------------------------------------------------------
total count = 84973549 (x = 102082303361, y = 201615400331)
---------------------------------------------------------------------------
total count = 84460132 (x = 218160455166, y = 711722577429)
---------------------------------------------------------------------------
total count = 2232978619 (x = 469765610637, y = 595836773324)
---------------------------------------------------------------------------
total count = 52919985 (x = 547789308293, y = 991485437316)
---------------------------------------------------------------------------
total count = 13047 (x = 251960980992, y = 110437930487)
---------------------------------------------------------------------------
total count = 7636675150 (x = 613835143328, y = 772626806894)
---------------------------------------------------------------------------
total count = 1460612 (x = 680906312440, y = 837046443297)
---------------------------------------------------------------------------
total count = 1353176 (x = 872779806678, y = 710729136214)
---------------------------------------------------------------------------
total count = 532279108 (x = 371852342607, y = 665991940633)
---------------------------------------------------------------------------
total count = 544330 (x = 362401211485, y = 128830665344)
---------------------------------------------------------------------------
total count = 323061 (x = 180666258693, y = 57131051343)
---------------------------------------------------------------------------
total count = 159430732 (x = 70946658128, y = 853553501163)
---------------------------------------------------------------------------
total count = 1238206 (x = 436180262598, y = 446206688642)
---------------------------------------------------------------------------
total count = 609877463 (x = 538117802412, y = 293149060799)
---------------------------------------------------------------------------
total count = 140506 (x = 634701255137, y = 531552734417)
---------------------------------------------------------------------------
total count = 34193941 (x = 452858449590, y = 263102219355)
---------------------------------------------------------------------------
total count = 8280634 (x = 383663692541, y = 57094573336)
---------------------------------------------------------------------------
total count = 11259717 (x = 425790820351, y = 784739637724)
---------------------------------------------------------------------------
total count = 45067 (x = 595525663833, y = 454523339873)
---------------------------------------------------------------------------
total count = 19537512 (x = 281874773365, y = 290222242493)
---------------------------------------------------------------------------
total count = 3380690 (x = 450854351139, y = 822598360795)
---------------------------------------------------------------------------
total count = 167235989482 (x = 696862211687, y = 432049100584)
---------------------------------------------------------------------------
total count = 31747189 (x = 54191700155, y = 348686561264)
---------------------------------------------------------------------------
total count = 20400 (x = 195740782707, y = 917131200677)
---------------------------------------------------------------------------
total count = 16092 (x = 766735965477, y = 414120809680)
---------------------------------------------------------------------------
total count = 349645 (x = 916448309897, y = 986336052522)
---------------------------------------------------------------------------
total count = 1127989211 (x = 948007261766, y = 742589144022)
---------------------------------------------------------------------------
total count = 94772242 (x = 279767594859, y = 995562476691)
---------------------------------------------------------------------------
total count = 64964 (x = 185202004843, y = 827927039657)
---------------------------------------------------------------------------
total count = 44217863289 (x = 388103969958, y = 132653589867)
---------------------------------------------------------------------------
total count = 89480120547 (x = 676386305140, y = 382933212843)
---------------------------------------------------------------------------
total count = 51129 (x = 130807371105, y = 263692273882)
---------------------------------------------------------------------------
total count = 9479 (x = 94135022763, y = 529502590496)
---------------------------------------------------------------------------
total count = 40978844926 (x = 388738573950, y = 432208540079)
---------------------------------------------------------------------------
total count = 39207003 (x = 137851822548, y = 556473635232)
---------------------------------------------------------------------------
total count = 18057387 (x = 657861403888, y = 455391598262)
---------------------------------------------------------------------------
total count = 164076454829 (x = 809879203020, y = 594611620289)
---------------------------------------------------------------------------

@gunslinger · 09.06.2023, 14:20

Небольшая поправка - код

C++

1	if (min >= dif)

нужно изменить на

C++

1	if (min >= dif && dif > 1)

Если кому вдруг интересно, программа (с промежуточным выводом, далее - ПВ) ниже в zip-архиве.
Значения x и y - "случайные" числа, не превышающие 10⁶, иначе ПВ может быть долгим (но без ПВ даже для чисел порядка 10¹² результаты выдаются за доли секунды).

@alexu_007 · 09.06.2023, 16:41

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

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

Тупо перебором. Потому что непонятно, в какой момент "вылезет" следующий НОД.

@gunslinger · 09.06.2023, 17:55

Следующий НОД вылезет, как я написал выше, минимум в двух случаях (про другие ситуации не знаю):

1) если выражение (|x - y| / НОД) не является простым числом (причем, используя способ деления x и y на НОД, можно узнать, через сколько шагов максимум НОД изменится (увеличится) - нужно найти делитель (провести факторизацию) выражения (|x - y| / НОД); точное значение шагов до изменения НОД тут, кроме того же перебора, хз как определить);

2) если выражение (|x - y| / НОД) - простое число или |x - y| = 1, то количество шагов до следующего изменения (увеличения) НОД можно найти так

C++

1 2	if (min >= dif) tmp = min - (min / dif) * dif, x -= tmp, y -= tmp, count += tmp / num;

где

C++

1	ull min = x < y ? x : y, max = x > y ? x : y, dif = max - min, tmp;

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

@alexu_007 715 / 675 / 110 Регистрация: 29.05.2015 Сообщений: 4,068
	07.06.2023, 13:15	21
	1. Обычный цикл в любом случае быстрее рекурсии. 2. НОД меняется. Это видно на листинге работы программы. Для примера для чисел 9876543210 и 1234567890. НОД растёт 90 - 360 - 1080 - 11880 - 2150280. Последнее значение максимальное и его программа вычитает до нуля. При получении максимального значения НОД дальше можно не вычитать, результат вычисляется по формуле: 1232110440 / 2150280 + 37 = 610 Проблема только в том, как узнать что НОД максимальный и дальше расти не будет? Миниатюры 1

@gunslinger случайный прохожий 3025 / 2056 / 624 Регистрация: 20.07.2013 Сообщений: 5,524
	07.06.2023, 15:52	22
	Что НОД может меняться, я даже и не предполагал (век живи, век учись). Сообщение от alexu_007 Проблема только в том, как узнать что НОД максимальный и дальше расти не будет? А вот это хороший вопрос (не зря, получается, слово "олимпиадная" в заголовке темы). Но идей пока нет. Добавлено через 9 минут Возможно, через какие-то свойства НОД? Например, Если m – любое натуральное число, то НОД(m·a, m·b)=m·НОД(a, b). Только чем это поможет? Короче, надо думать (если получится). Добавлено через 1 час 42 минуты Еще есть предположение, что нужно не просто понять, когда НОД достиг максимума, но и в принципе определять ситуации с повторением НОД (до его возможного увеличения). Вроде кажется, что разгадка близка, но пока ускользает. данные count = 0 ::::: gcd(9876543210, 1234567890) = 90 ::::: (x / gcd) and (y / gcd) = 109739369 and 13717421 count = 1 ::::: gcd(9876543120, 1234567800) = 360 ::::: (x / gcd) and (y / gcd) = 27434842 and 3429355 count = 2 ::::: gcd(9876542760, 1234567440) = 1080 ::::: (x / gcd) and (y / gcd) = 9144947 and 1143118 count = 3 ::::: gcd(9876541680, 1234566360) = 1080 ::::: (x / gcd) and (y / gcd) = 9144946 and 1143117 count = 4 ::::: gcd(9876540600, 1234565280) = 1080 ::::: (x / gcd) and (y / gcd) = 9144945 and 1143116 count = 5 ::::: gcd(9876539520, 1234564200) = 1080 ::::: (x / gcd) and (y / gcd) = 9144944 and 1143115 count = 6 ::::: gcd(9876538440, 1234563120) = 1080 ::::: (x / gcd) and (y / gcd) = 9144943 and 1143114 count = 7 ::::: gcd(9876537360, 1234562040) = 1080 ::::: (x / gcd) and (y / gcd) = 9144942 and 1143113 count = 8 ::::: gcd(9876536280, 1234560960) = 1080 ::::: (x / gcd) and (y / gcd) = 9144941 and 1143112 count = 9 ::::: gcd(9876535200, 1234559880) = 1080 ::::: (x / gcd) and (y / gcd) = 9144940 and 1143111 count = 10 ::::: gcd(9876534120, 1234558800) = 1080 ::::: (x / gcd) and (y / gcd) = 9144939 and 1143110 count = 11 ::::: gcd(9876533040, 1234557720) = 11880 ::::: (x / gcd) and (y / gcd) = 831358 and 103919 count = 12 ::::: gcd(9876521160, 1234545840) = 11880 ::::: (x / gcd) and (y / gcd) = 831357 and 103918 count = 13 ::::: gcd(9876509280, 1234533960) = 11880 ::::: (x / gcd) and (y / gcd) = 831356 and 103917 count = 14 ::::: gcd(9876497400, 1234522080) = 11880 ::::: (x / gcd) and (y / gcd) = 831355 and 103916 count = 15 ::::: gcd(9876485520, 1234510200) = 11880 ::::: (x / gcd) and (y / gcd) = 831354 and 103915 count = 16 ::::: gcd(9876473640, 1234498320) = 11880 ::::: (x / gcd) and (y / gcd) = 831353 and 103914 count = 17 ::::: gcd(9876461760, 1234486440) = 11880 ::::: (x / gcd) and (y / gcd) = 831352 and 103913 count = 18 ::::: gcd(9876449880, 1234474560) = 11880 ::::: (x / gcd) and (y / gcd) = 831351 and 103912 count = 19 ::::: gcd(9876438000, 1234462680) = 11880 ::::: (x / gcd) and (y / gcd) = 831350 and 103911 count = 20 ::::: gcd(9876426120, 1234450800) = 11880 ::::: (x / gcd) and (y / gcd) = 831349 and 103910 count = 21 ::::: gcd(9876414240, 1234438920) = 11880 ::::: (x / gcd) and (y / gcd) = 831348 and 103909 count = 22 ::::: gcd(9876402360, 1234427040) = 11880 ::::: (x / gcd) and (y / gcd) = 831347 and 103908 count = 23 ::::: gcd(9876390480, 1234415160) = 11880 ::::: (x / gcd) and (y / gcd) = 831346 and 103907 count = 24 ::::: gcd(9876378600, 1234403280) = 11880 ::::: (x / gcd) and (y / gcd) = 831345 and 103906 count = 25 ::::: gcd(9876366720, 1234391400) = 11880 ::::: (x / gcd) and (y / gcd) = 831344 and 103905 count = 26 ::::: gcd(9876354840, 1234379520) = 11880 ::::: (x / gcd) and (y / gcd) = 831343 and 103904 count = 27 ::::: gcd(9876342960, 1234367640) = 11880 ::::: (x / gcd) and (y / gcd) = 831342 and 103903 count = 28 ::::: gcd(9876331080, 1234355760) = 11880 ::::: (x / gcd) and (y / gcd) = 831341 and 103902 count = 29 ::::: gcd(9876319200, 1234343880) = 11880 ::::: (x / gcd) and (y / gcd) = 831340 and 103901 count = 30 ::::: gcd(9876307320, 1234332000) = 11880 ::::: (x / gcd) and (y / gcd) = 831339 and 103900 count = 31 ::::: gcd(9876295440, 1234320120) = 11880 ::::: (x / gcd) and (y / gcd) = 831338 and 103899 count = 32 ::::: gcd(9876283560, 1234308240) = 11880 ::::: (x / gcd) and (y / gcd) = 831337 and 103898 count = 33 ::::: gcd(9876271680, 1234296360) = 11880 ::::: (x / gcd) and (y / gcd) = 831336 and 103897 count = 34 ::::: gcd(9876259800, 1234284480) = 11880 ::::: (x / gcd) and (y / gcd) = 831335 and 103896 count = 35 ::::: gcd(9876247920, 1234272600) = 11880 ::::: (x / gcd) and (y / gcd) = 831334 and 103895 count = 36 ::::: gcd(9876236040, 1234260720) = 2150280 ::::: (x / gcd) and (y / gcd) = 4593 and 574 count = 37 ::::: gcd(9874085760, 1232110440) = 2150280 ::::: (x / gcd) and (y / gcd) = 4592 and 573 count = 38 ::::: gcd(9871935480, 1229960160) = 2150280 ::::: (x / gcd) and (y / gcd) = 4591 and 572 count = 39 ::::: gcd(9869785200, 1227809880) = 2150280 ::::: (x / gcd) and (y / gcd) = 4590 and 571 count = 40 ::::: gcd(9867634920, 1225659600) = 2150280 ::::: (x / gcd) and (y / gcd) = 4589 and 570 count = 41 ::::: gcd(9865484640, 1223509320) = 2150280 ::::: (x / gcd) and (y / gcd) = 4588 and 569 count = 42 ::::: gcd(9863334360, 1221359040) = 2150280 ::::: (x / gcd) and (y / gcd) = 4587 and 568 count = 43 ::::: gcd(9861184080, 1219208760) = 2150280 ::::: (x / gcd) and (y / gcd) = 4586 and 567 count = 44 ::::: gcd(9859033800, 1217058480) = 2150280 ::::: (x / gcd) and (y / gcd) = 4585 and 566 count = 45 ::::: gcd(9856883520, 1214908200) = 2150280 ::::: (x / gcd) and (y / gcd) = 4584 and 565 ................................................................................ ................................................................... данные с учетом вышеуказанного свойства НОД count = 0 ::::: gcd(9876543210, 1234567890) = 90 ::::: (x / gcd) and (y / gcd) = 109739369 and 13717421 count = 1 ::::: gcd(109739368, 13717420) = 4 ::::: (x / gcd) and (y / gcd) = 27434842 and 3429355 count = 2 ::::: gcd(27434841, 3429354) = 3 ::::: (x / gcd) and (y / gcd) = 9144947 and 1143118 count = 3 ::::: gcd(9144946, 1143117) = 1 ::::: (x / gcd) and (y / gcd) = 9144946 and 1143117 count = 4 ::::: gcd(9144945, 1143116) = 1 ::::: (x / gcd) and (y / gcd) = 9144945 and 1143116 count = 5 ::::: gcd(9144944, 1143115) = 1 ::::: (x / gcd) and (y / gcd) = 9144944 and 1143115 count = 6 ::::: gcd(9144943, 1143114) = 1 ::::: (x / gcd) and (y / gcd) = 9144943 and 1143114 count = 7 ::::: gcd(9144942, 1143113) = 1 ::::: (x / gcd) and (y / gcd) = 9144942 and 1143113 count = 8 ::::: gcd(9144941, 1143112) = 1 ::::: (x / gcd) and (y / gcd) = 9144941 and 1143112 count = 9 ::::: gcd(9144940, 1143111) = 1 ::::: (x / gcd) and (y / gcd) = 9144940 and 1143111 count = 10 ::::: gcd(9144939, 1143110) = 1 ::::: (x / gcd) and (y / gcd) = 9144939 and 1143110 count = 11 ::::: gcd(9144938, 1143109) = 11 ::::: (x / gcd) and (y / gcd) = 831358 and 103919 count = 12 ::::: gcd(831357, 103918) = 1 ::::: (x / gcd) and (y / gcd) = 831357 and 103918 count = 13 ::::: gcd(831356, 103917) = 1 ::::: (x / gcd) and (y / gcd) = 831356 and 103917 count = 14 ::::: gcd(831355, 103916) = 1 ::::: (x / gcd) and (y / gcd) = 831355 and 103916 count = 15 ::::: gcd(831354, 103915) = 1 ::::: (x / gcd) and (y / gcd) = 831354 and 103915 count = 16 ::::: gcd(831353, 103914) = 1 ::::: (x / gcd) and (y / gcd) = 831353 and 103914 count = 17 ::::: gcd(831352, 103913) = 1 ::::: (x / gcd) and (y / gcd) = 831352 and 103913 count = 18 ::::: gcd(831351, 103912) = 1 ::::: (x / gcd) and (y / gcd) = 831351 and 103912 count = 19 ::::: gcd(831350, 103911) = 1 ::::: (x / gcd) and (y / gcd) = 831350 and 103911 count = 20 ::::: gcd(831349, 103910) = 1 ::::: (x / gcd) and (y / gcd) = 831349 and 103910 count = 21 ::::: gcd(831348, 103909) = 1 ::::: (x / gcd) and (y / gcd) = 831348 and 103909 count = 22 ::::: gcd(831347, 103908) = 1 ::::: (x / gcd) and (y / gcd) = 831347 and 103908 count = 23 ::::: gcd(831346, 103907) = 1 ::::: (x / gcd) and (y / gcd) = 831346 and 103907 count = 24 ::::: gcd(831345, 103906) = 1 ::::: (x / gcd) and (y / gcd) = 831345 and 103906 count = 25 ::::: gcd(831344, 103905) = 1 ::::: (x / gcd) and (y / gcd) = 831344 and 103905 count = 26 ::::: gcd(831343, 103904) = 1 ::::: (x / gcd) and (y / gcd) = 831343 and 103904 count = 27 ::::: gcd(831342, 103903) = 1 ::::: (x / gcd) and (y / gcd) = 831342 and 103903 count = 28 ::::: gcd(831341, 103902) = 1 ::::: (x / gcd) and (y / gcd) = 831341 and 103902 count = 29 ::::: gcd(831340, 103901) = 1 ::::: (x / gcd) and (y / gcd) = 831340 and 103901 count = 30 ::::: gcd(831339, 103900) = 1 ::::: (x / gcd) and (y / gcd) = 831339 and 103900 count = 31 ::::: gcd(831338, 103899) = 1 ::::: (x / gcd) and (y / gcd) = 831338 and 103899 count = 32 ::::: gcd(831337, 103898) = 1 ::::: (x / gcd) and (y / gcd) = 831337 and 103898 count = 33 ::::: gcd(831336, 103897) = 1 ::::: (x / gcd) and (y / gcd) = 831336 and 103897 count = 34 ::::: gcd(831335, 103896) = 1 ::::: (x / gcd) and (y / gcd) = 831335 and 103896 count = 35 ::::: gcd(831334, 103895) = 1 ::::: (x / gcd) and (y / gcd) = 831334 and 103895 count = 36 ::::: gcd(831333, 103894) = 181 ::::: (x / gcd) and (y / gcd) = 4593 and 574 count = 37 ::::: gcd(4592, 573) = 1 ::::: (x / gcd) and (y / gcd) = 4592 and 573 count = 38 ::::: gcd(4591, 572) = 1 ::::: (x / gcd) and (y / gcd) = 4591 and 572 count = 39 ::::: gcd(4590, 571) = 1 ::::: (x / gcd) and (y / gcd) = 4590 and 571 count = 40 ::::: gcd(4589, 570) = 1 ::::: (x / gcd) and (y / gcd) = 4589 and 570 count = 41 ::::: gcd(4588, 569) = 1 ::::: (x / gcd) and (y / gcd) = 4588 and 569 count = 42 ::::: gcd(4587, 568) = 1 ::::: (x / gcd) and (y / gcd) = 4587 and 568 count = 43 ::::: gcd(4586, 567) = 1 ::::: (x / gcd) and (y / gcd) = 4586 and 567 count = 44 ::::: gcd(4585, 566) = 1 ::::: (x / gcd) and (y / gcd) = 4585 and 566 count = 45 ::::: gcd(4584, 565) = 1 ::::: (x / gcd) and (y / gcd) = 4584 and 565 ................................................................................ ................................................................... 0

@gunslinger случайный прохожий 3025 / 2056 / 624 Регистрация: 20.07.2013 Сообщений: 5,524
	07.06.2023, 19:03	23
	Нашел такое свойство: Может его как-то получится использовать? У меня идей больше нет. 0

@alexu_007 715 / 675 / 110 Регистрация: 29.05.2015 Сообщений: 4,068
	08.06.2023, 16:51	25
	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 total count = 729582 В этом тесте у меня получился другой результат: Миниатюры 1

@gunslinger случайный прохожий 3025 / 2056 / 624 Регистрация: 20.07.2013 Сообщений: 5,524
	08.06.2023, 19:20	26
	Если я правильно понял, ты вычитаешь НОД из x и y, а нужно делить x и y на НОД. Верно? 0

@alexu_007 715 / 675 / 110 Регистрация: 29.05.2015 Сообщений: 4,068
	08.06.2023, 19:35	27
	Так вроде в задании? В задачке давалось два числа x и y. Леброну надо было повторять следующую операцию, пока x и y больше или равны 1. Заменим x и y на x−t и y−t соответственно, где t — НОД(x, y). 0

@alexu_007 715 / 675 / 110 Регистрация: 29.05.2015 Сообщений: 4,068
	09.06.2023, 06:54	29
	Сообщение от gunslinger Если не секрет, как у тебя последняя строка в примере формируется? Если скан из поста 25, то там выводятся только те строки, где меняется НОД. Изначальный НОД = 0, поэтому в первом действии он меняется на 1 и выводится на экран в виде: счётчик - НОД - (X-НОД) - (Y-НОД). Далее, X и Y после вычитания единицы становятся чётными - НОД становится равным 2. После вычитания 2 НОД становится равным 20, и снова вывод на экран. После вычитания 20 НОД становится равным 560 и остаётся таким в течение 101681 шагов - столько раз из X и Y вычитается 560. И на последнем шаге НОД становится равным 17581440. 1

@gunslinger случайный прохожий 3025 / 2056 / 624 Регистрация: 20.07.2013 Сообщений: 5,524
	09.06.2023, 12:58	31
	Еще пара результатов: count = 0 ::::: gcd(375412775, 66439544) = 1 ::::: (x / gcd) and (y / gcd) = 375412775 and 66439544 count = 1 ::::: gcd(375412774, 66439543) = 1 ::::: (x / gcd) and (y / gcd) = 375412774 and 66439543 count = 2 ::::: gcd(375412773, 66439542) = 57 ::::: (x / gcd) and (y / gcd) = 6586189 and 1165606 count = 3 ::::: gcd(6586188, 1165605) = 21 ::::: (x / gcd) and (y / gcd) = 313628 and 55505 count = 4 ::::: gcd(313627, 55504) = 1 ::::: (x / gcd) and (y / gcd) = 313627 and 55504 count = 5 ::::: gcd(313626, 55503) = 3 ::::: (x / gcd) and (y / gcd) = 104542 and 18501 count = 6 ::::: gcd(104541, 18500) = 1 ::::: (x / gcd) and (y / gcd) = 104541 and 18500 count = 7 ::::: gcd(104540, 18499) = 1 ::::: (x / gcd) and (y / gcd) = 104540 and 18499 count = 8 ::::: gcd(104539, 18498) = 1 ::::: (x / gcd) and (y / gcd) = 104539 and 18498 count = 9 ::::: gcd(104538, 18497) = 1 ::::: (x / gcd) and (y / gcd) = 104538 and 18497 count = 10 ::::: gcd(104537, 18496) = 1 ::::: (x / gcd) and (y / gcd) = 104537 and 18496 count = 11 ::::: gcd(104536, 18495) = 1 ::::: (x / gcd) and (y / gcd) = 104536 and 18495 count = 12 ::::: gcd(104535, 18494) = 1 ::::: (x / gcd) and (y / gcd) = 104535 and 18494 count = 13 ::::: gcd(104534, 18493) = 1 ::::: (x / gcd) and (y / gcd) = 104534 and 18493 count = 14 ::::: gcd(104533, 18492) = 1 ::::: (x / gcd) and (y / gcd) = 104533 and 18492 count = 15 ::::: gcd(104532, 18491) = 1 ::::: (x / gcd) and (y / gcd) = 104532 and 18491 count = 16 ::::: gcd(104531, 18490) = 1 ::::: (x / gcd) and (y / gcd) = 104531 and 18490 count = 17 ::::: gcd(104530, 18489) = 1 ::::: (x / gcd) and (y / gcd) = 104530 and 18489 count = 18 ::::: gcd(104529, 18488) = 1 ::::: (x / gcd) and (y / gcd) = 104529 and 18488 count = 19 ::::: gcd(104528, 18487) = 139 ::::: (x / gcd) and (y / gcd) = 752 and 133 count = 20 ::::: gcd(751, 132) = 1 ::::: (x / gcd) and (y / gcd) = 751 and 132 --------------------------------------------------------------------------- total count = 152 (x = 375412775, y = 66439544) и 0

@alexu_007 715 / 675 / 110 Регистрация: 29.05.2015 Сообщений: 4,068
	09.06.2023, 16:41	34
	Сообщение от gunslinger Как удалось определить значение количества шагов - по какой-то формуле или просто следуя "точному алгоритму задачи" (поэтапно вычитая НОД и высчитывая его значение повторно)? Тупо перебором. Потому что непонятно, в какой момент "вылезет" следующий НОД. 1