Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).
Задача
Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.
Входные данные
Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].
Выходные данные
[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].Тесты
Входные данные | Выходные данные | ||||
---|---|---|---|---|---|
2 | 3 | 4 | 1 | ||
2 | 4 | 8 | 4 | ||
4 | 24 | 23 | 40 | 90 | 1 |
4 | 36 | 48 | 20 | 24 | 4 |
3 | 30 | 738 | 1926 | 6 |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; unsigned long long gcd(unsigned long long m, unsigned long long n) { return (n != 0) ? gcd(n, m%n) : m; } int main() { unsigned long long m, n, result; cin >> m >> result; for (unsigned long long i = 2; i <= m; i++) { cin >> n; result = gcd(result, n); if (result == 1) m = 1; //same as break } cout << result << endl; return 0; } |
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 |
import java.util.*; public class Main { public static long gcd(long m, long n) { if (n != 0) return gcd(n, m%n); else return m; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); long m = in.nextLong(), n, result = in.nextLong(); for(long i = 2; i <= m; ++i) { n = in.nextLong(); result = gcd(result, n); if (result == 1) m = 1; //same as break } System.out.println(result); } } |
Решение задачи
Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную
m число [latex]m[/latex], а в
result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную
n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную
result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.
Ссылки
- Условие задачи (страница 137);
- Код программы на С++;
- Код программы на Java.
— Функция gcd_inner() отлично справляется со своей задачей независимо от того, какой из аргументов больше.
— Если на каком-то этапе gcd = 1, то дальше что-то проверять нет смысла — ответ уже ясен.
Спасибо. Исправил.