Задача
Найти НОД (наибольший общий делитель ) $n$ чисел.
Входные данные
Первая строка содержит количество чисел [latex]n \left(1 < n < 101\right)[/latex]. Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает [latex]30000[/latex].
Выходные данные
НОД заданных чисел.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 5 7 2 |
1 |
| 2 | 2 45 10 |
5 |
| 3 | 4 27 90 15 9 |
3 |
| 4 | 2 40 64 |
8 |
| 5 | 3 8 8 8 |
8 |
Код
|
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.io.*; import java.util.Scanner; class GCD { public static int gcd(int a,int b) { while (b !=0) { int tmp = a%b; a = b; b = tmp; } return a; } } class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int t = in.nextInt(); int b = in.nextInt(); for (int i=2; i<=t; ++i) { int a = in.nextInt(); b = GCD.gcd (a, b); } System.out.print(b); } } |
Решение задачи
Для решения данной задачи воспользуемся алгоритмом Евклида — алгоритмом нахождения наибольшего общего делителя (НОД) пары целых чисел, т.е. самого большого числа, на которое можно без остатка разделить оба числа, для которых ищется НОД.
И снова…