Я могу рассчитать GCD двух чисел. заданное множество S = {1,2,3,4,5}, и я должен вычислить GCD каждой пары, как {1,2} = 1, {1,3} = 1, {1,4} = 1 , {1,5} = 1, {2,3} = 1, {2,4} = 2, {2,5} = 1 и т. Д. Я знаю решение O (N^2), просто вычислив GCD каждой пары, которая даст мне TLE в случае большого набора для 2 < = n < = 10^9 или более, но я хочу узнать O (N * sqrt (N)) или лучше. Я хочу GCD каждой пары отдельно.Как найти GCD некоторых пар чисел заданного набора?
Вы можете написать программу с Euclidean algorithm
Ознакомьтесь пример поиска GCD(1071,462)
НОД {1,2,3,4,5} = НОД {НОД {НОД {1,2}, НОД {3,4}}, 5}
использование Euclidean algorithm 4 раза только calclate НОД данного множества S = {1,2,3,4,5}
с помощью евклидовой, единственный вам нужно будет найти напоминания, пока номер не исчезнет.
Базовый алгоритм Евклида поможет.
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b%a, a);
}
Интересно, если вы хотите найти GCD всего комплекта. Все, что вам нужно сделать, это сформировать подмножество из полученного GCD и повторить, если осталось только 1 конечный элемент. например S={1,2,3,4,5} => S1={GCD(1,2) , GCD(3,4) , add 5 } => S2={GCD(1,1) , and 5 } => S3={GCD(1,5)} => 1
но, возможно, это не O (N * SQRT (п) решение. Я хочу НОД каждой пары в отдельности. Я не не хочу НОД всего набора. –
@RazibHossainShuvo Почему вам нужно что если у вас есть лучшее решение? –