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

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

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

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

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

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

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

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

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


Пробовал сделать в тупую - ожидаемо не проходит по времени. Больше идей нет
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.06.2023, 18:15
Ответы с готовыми решениями:

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

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

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

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

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

1232110440 / 2150280 + 37 = 610

Проблема только в том, как узнать что НОД максимальный и дальше расти не будет?
Миниатюры
Олимпиадная задача про НОД  
1
случайный прохожий
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
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
07.06.2023, 19:03 23
Нашел такое свойство:
Олимпиадная задача про НОД

Может его как-то получится использовать? У меня идей больше нет.
0
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
08.06.2023, 04:14 24
Цитата Сообщение от alexu_007 Посмотреть сообщение
Проблема только в том, как узнать что НОД максимальный и дальше расти не будет?
Я, кажется, понял. После каждого нахождения НОД делим x и y на НОД, получая новые значения x и y.
Если НОД = 1 (в какой-то момент), то далее вычисляем |x - y|. Если эта разница равна 1 или является простым числом, то к счетчику операций добавляем минимальное из двух чисел x и y. Это и будет ответ. Код ниже.
C++
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
37
38
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}
1
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
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
08.06.2023, 19:20 26
Если я правильно понял, ты вычитаешь НОД из x и y, а нужно делить x и y на НОД. Верно?
0
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
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
08.06.2023, 21:12 28
Это понятно. Я просто почему-то подумал, что ты используешь решение через сокращение x и y на НОД с дальнейшим декрементом x и y (полагал, что так проще).
C++
1
2
3
4
    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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)
0
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
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
09.06.2023, 12:43 30
Да, я про пост №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++
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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)
1
случайный прохожий
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
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
09.06.2023, 13:10 32
И просто результаты (без промежуточных):
здесь
---------------------------------------------------------------------------
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)
---------------------------------------------------------------------------
0
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
09.06.2023, 14:20 33
Небольшая поправка - код
C++
1
  if (min >= dif)
нужно изменить на
C++
1
  if (min >= dif && dif > 1)
Если кому вдруг интересно, программа (с промежуточным выводом, далее - ПВ) ниже в zip-архиве.
Значения x и y - "случайные" числа, не превышающие 106, иначе ПВ может быть долгим (но без ПВ даже для чисел порядка 1012 результаты выдаются за доли секунды).

Олимпиадная задача про НОД
Вложения
Тип файла: zip gcd_ops_cnt.zip (1.36 Мб, 3 просмотров)
1
715 / 675 / 110
Регистрация: 29.05.2015
Сообщений: 4,068
09.06.2023, 16:41 34
Цитата Сообщение от gunslinger Посмотреть сообщение
Как удалось определить значение количества шагов - по какой-то формуле или просто следуя "точному алгоритму задачи" (поэтапно вычитая НОД и высчитывая его значение повторно)?
Тупо перебором. Потому что непонятно, в какой момент "вылезет" следующий НОД.
1
случайный прохожий
3025 / 2056 / 624
Регистрация: 20.07.2013
Сообщений: 5,524
09.06.2023, 17:55 35
Следующий НОД вылезет, как я написал выше, минимум в двух случаях (про другие ситуации не знаю):

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;
1
09.06.2023, 17:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.06.2023, 17:55
Помогаю со студенческими работами здесь

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

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

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

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

Олимпиадная задача
Не могу решить эту задачу уже 3 дня, не понимаю в чем логика, может быть кто-то догадается и сможет...

Олимпиадная задача
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо...

Олимпиадная задача
Задача A. Олимпиада Маленький мальчик Гриша уже сам начал делать олимпиады, и ему как раз нужно...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru