4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
1

Быстрое вычисление наибольшего общего делителя для unsigned long long int

01.12.2014, 08:02. Показов 1324. Ответов 12
Метки нет (Все метки)

Даны два числа типа unsigned long long int, в них могут оказаться любые представимые значения, требуется максимально быстро вычислить наибольший общий делитель.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.12.2014, 08:02
Ответы с готовыми решениями:

Требуется написать функцию long long pow(long long a, unsigned int p), которая возводит число a в степень p
Требуется написать функцию long long pow(long long a, unsigned int p), которая возводит число a в...

Не понятный undefined reference to `unsigned long long f<unsigned long long, void>
test.cpp: #include &lt;iostream&gt; template &lt;typename FormalType, typename FactType = typename...

Перевести long long unsigned int в массив char
Подскажите, пожалуйста, как превратить число типа long long unsigned int в массив символов? Каждый...

Работа с unsigned long long int на 32-битных системах
В программе испольуется тип данных unsigned long int, но в некоторых (хотя и очень редких) случаях...

12
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
17781 / 10545 / 2035
Регистрация: 27.09.2012
Сообщений: 26,514
Записей в блоге: 1
01.12.2014, 10:32 4
Цитата Сообщение от taras atavin Посмотреть сообщение
Или Вы о чём?
Википедия: Алгоритм Евклида
0
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
01.12.2014, 10:57  [ТС] 5
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Одно число 2 701 703 435 345 984 178, второе 15, искомое число 3. Сколько раз вычитать будем? А перебирать все меньшие числа плохо, когда оба числа большие.
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.12.2014, 11:03 6
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
using namespace std;
 
typedef unsigned long long uli;
 
uli gcd(uli a, uli b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
 
int main(){
 
    uli a, b;
    cin >> a >> b;
    uli g = gcd(a, b);
    cout << g << endl;
 
    return 0;
}

если из числа А много раз вычитать число Б пока оно не станет меньше, в итоге получим число А % Б.
0
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
01.12.2014, 12:35  [ТС] 7
Цитата Сообщение от SlavaSSU Посмотреть сообщение
uli gcd(uli a, uli b) { if(b == 0) return a; return gcd(b, a % b); }
Какова максимальная глубина рекурсии?

Добавлено через 5 минут
И может тогда уж так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned long long int nod(unsigned long long int a, unsigned long long int b)
{
 unsigned long long int c;
 if (a<b)
 {
  c=a;
  a=b;
  b=c;
 }
 while (b!=0)
 {
  c=a%b;
  a=b;
  b=c;
 }
 return a;
}
.

Добавлено через 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))) он работает евклид.


насчет второго есть предположение.

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cassert>
 
using namespace std;
 
typedef unsigned long long uli;
 
uli gcd(uli a, uli b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
 
uli naive(uli a, uli b, uli c, uli d)
{
    return gcd(a * b, c * d);
}
 
int main(){
 
    uli a, b, c, d;
    cin >> a >> b >> c >> d;
    assert(gcd(a, b) == 1);
    assert(gcd(c, d) == 1);
 
    uli g = gcd(a, c) * gcd(a, d) * gcd(b, c) * gcd(b, d);
    cout << "answer is " << gcd(a, c) << " * " << gcd(a, d) << " * " << gcd(b, c) << " * " << gcd(b, d) << endl;
    cout << g << endl;
    cerr << naive(a, b, c, d) << endl;
 
    return 0;
}
Добавлено через 6 минут
я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро.
0
4202 / 1794 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
01.12.2014, 13:44  [ТС] 9
Цитата Сообщение от SlavaSSU Посмотреть сообщение
uli naive(uli a, uli b, uli c, uli d) { return gcd(a * b, c * d); }
При вычислении произведений может произойти переполнение типа. Поэтому условие:
Цитата Сообщение от taras atavin Посмотреть сообщение
но в явном виде эти произведения не вычислять.
. В то же время a может иметь достаточно большой общий делитель с d, а с хорошо делиться на b.

Добавлено через 1 минуту
Цитата Сообщение от SlavaSSU Посмотреть сообщение
я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро.
То есть максимум десятки шагов цикла?
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
Цитата Сообщение от SlavaSSU Посмотреть сообщение
uli a, b, c, d; cin >> a >> b >> c >> d; assert(gcd(a, b) == 1); assert(gcd(c, d) == 1);
Ты не понял. Числа не сами по себе, это числитель и знаменатель дроби и она уже сокращена. Задачи такие:
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
Цитата Сообщение от SlavaSSU Посмотреть сообщение
taras atavin, просто привычка иногда проверять входные данные на корректность.
Для задачи они корректны и при несоответствии указанному ограничению. Ограничение возникло просто из порядка решения указанных задач. Все четыре лежат в двух приватных полях двух объектов, поля присваиваются только конструктором, он сначала считает НОД, потом делит на него оба числа и только после этого присваиваются.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.12.2014, 14:03
Помогаю со студенческими работами здесь

Размер для данных (int, char, long, double, short, unsigned, float)
Напишите программу, которая будет определять размер для данных (int, char, long, double, short,...

Меняется ответ при приведении функции pow к unsigned long long
Тест: 50 50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

Написать функцию, которая принимает два параметра типа unsigned long long и выводит их на экран
Я самое наглое , ленивое и бессовестное чудовище)) но тем не менее Напишите функцию, которая ...

Как преобразовать char[8] к unsigned long long?
Требуется выполнить преобразование char к unsigned long long и обратно


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

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

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