4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
1 | |
Быстрое вычисление наибольшего общего делителя для unsigned long long int01.12.2014, 08:02. Показов 1324. Ответов 12
Метки нет Все метки)
(
Даны два числа типа unsigned long long int, в них могут оказаться любые представимые значения, требуется максимально быстро вычислить наибольший общий делитель.
0
|
|
01.12.2014, 08:02 | |
Ответы с готовыми решениями:
12
Требуется написать функцию long long pow(long long a, unsigned int p), которая возводит число a в степень p Не понятный undefined reference to `unsigned long long f<unsigned long long, void>
|
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
01.12.2014, 09:01 | 2 |
taras atavin, я может туплю(скорее всего), но чем Евклид не подходит?
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
01.12.2014, 10:29 [ТС] | 3 |
А при чём здесь геометрия? Или Вы о чём?
0
|
Don't worry, be happy
|
|
01.12.2014, 10:32 | 4 |
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
01.12.2014, 10:57 [ТС] | 5 |
0
|
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
||||||
01.12.2014, 11:03 | 6 | |||||
если из числа А много раз вычитать число Б пока оно не станет меньше, в итоге получим число А % Б.
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
||||||
01.12.2014, 12:35 [ТС] | 7 | |||||
Какова максимальная глубина рекурсии?
Добавлено через 5 минут И может тогда уж так:
Добавлено через 5 минут Вторая версия задачи. Даны четыре числа: a, b, c и d. Все четыре типа unsigned long long int и могут иметь любые представимые значения, но с одним ограничением: наибольший общий делителитель a и b равен 1 и наибольший общий делитель c и d равен 1. Требуется найти наибольший общий делитель произведений a*b и c*d (разрядностью по 128 бит каждое), но в явном виде эти произведения не вычислять.
0
|
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
||||||
01.12.2014, 13:41 | 8 | |||||
taras atavin, да без разницы рекурсивно писать или нет, все равно он быстро работает. там вроде O(log(log(max(a, b))) он работает евклид.
насчет второго есть предположение.
я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро.
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
01.12.2014, 13:44 [ТС] | 9 |
При вычислении произведений может произойти переполнение типа. Поэтому условие:
. В то же время a может иметь достаточно большой общий делитель с d, а с хорошо делиться на b.
Добавлено через 1 минуту То есть максимум десятки шагов цикла?
0
|
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
01.12.2014, 13:48 | 10 |
taras atavin, я понимаю что там все переполнится. это я тестил ччуть-чуть на небольших числах.
ну да, для чисел порядка 10^18 - 60 шагов. грубо говоря.
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
01.12.2014, 13:51 [ТС] | 11 |
Ты не понял. Числа не сами по себе, это числитель и знаменатель дроби и она уже сокращена. Задачи такие:
1. Упростить обыкновенную дробь, представленную числителем и знаменателем типа unsigned long long int. 2. Вычислить числитель и знаменатель упрощённой обыкновенной дроби, равной произведению двух дургих упрощённых обыкновенных дробей. НОД=1 именно потому, что операнды уже упрощены. Поэтому ни какого ассерта, просто a и b заранее поделены на наибольший общий делитель этой пары, а c и d заранее поделены на наибольший общий делитель второй пары.
0
|
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
01.12.2014, 13:54 | 12 |
taras atavin, просто привычка иногда проверять входные данные на корректность.
0
|
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
01.12.2014, 14:03 [ТС] | 13 |
Для задачи они корректны и при несоответствии указанному ограничению. Ограничение возникло просто из порядка решения указанных задач. Все четыре лежат в двух приватных полях двух объектов, поля присваиваются только конструктором, он сначала считает НОД, потом делит на него оба числа и только после этого присваиваются.
0
|
01.12.2014, 14:03 | |
Помогаю со студенческими работами здесь
13
Как преобразовать char[8] к unsigned long long? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |