Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
1

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

01.12.2014, 08:02. Показов 1024. Ответов 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
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.12.2014, 09:01 2
taras atavin, я может туплю(скорее всего), но чем Евклид не подходит?
0
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
01.12.2014, 10:29  [ТС] 3
А при чём здесь геометрия? Или Вы о чём?
0
Don't worry, be happy
17165 / 10049 / 1934
Регистрация: 27.09.2012
Сообщений: 25,035
Записей в блоге: 1
01.12.2014, 10:32 4
Цитата Сообщение от taras atavin Посмотреть сообщение
Или Вы о чём?
Википедия: Алгоритм Евклида
0
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
01.12.2014, 10:57  [ТС] 5
В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.
Одно число 2 701 703 435 345 984 178, второе 15, искомое число 3. Сколько раз вычитать будем? А перебирать все меньшие числа плохо, когда оба числа большие.
0
219 / 164 / 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
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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
219 / 164 / 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
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.12.2014, 13:48 10
taras atavin, я понимаю что там все переполнится. это я тестил ччуть-чуть на небольших числах.

ну да, для чисел порядка 10^18 - 60 шагов. грубо говоря.
0
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.12.2014, 13:54 12
taras atavin, просто привычка иногда проверять входные данные на корректность.
0
4200 / 1792 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
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® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.