C++
Сокращение последовательности
Дана последовательность натуральных чисел. Найдите наибольший общий делитель всех элементов последовательности и сократите все её члены на него.

Решение оформите в виде функции bool isDivisor(vector &A, int d), проверяющей является ли число d общим делителем последовательности, и функции void reduction(vector &A), которая находит наибольший общий делитель и сокращает все члены последовательности на него.

Входные данные

В первой строке входных данных записано натуральное число n (n≤100) — количество элементов последовательности. В следующей строке даны n натуральных чисел, не превышающих 10000, — элементы последовательности.

Выходные данные

Выведите n чисел — итоговую последовательность.

Примеры
Ввод
Вывод
5
3 6 9 12 18
1 2 3 4 6
2
57 179
57 179

C++




#include 
#include 
using namespace std;
// Проверяет, является ли d общим делителем всех элементов массива
bool isDivisor(vector<int> &A, int d) {
    for (int i = 0; i < A.size(); i++) {
        if (A[i] % d != 0)
            return false;
    }
    return true;
}
// Находит НОД всех элементов и сокращает последовательность
void reduction(vector<int> &A) {
    int gcd = 1;
    // Ищем наибольший общий делитель
    for (int d = 1; d <= 10000; d++) {
        if (isDivisor(A, d))
            gcd = d;
    }
    // Делим все элементы на найденный НОД
    for (int i = 0; i < A.size(); i++) {
        A[i] /= gcd;
    }
}
int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    reduction(A);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    return 0;
}

Объяснение:

Сначала создается функция isDivisor. Она получает последовательность и число d. Если каждый элемент последовательности делится на d без остатка, значит d является общим делителем, и функция возвращает true. Если хотя бы один элемент не делится, возвращается false.

В функции reduction перебираются все возможные делители от 1 до 10000. Каждый подходящий общий делитель сохраняется в переменную gcd, поэтому в конце там остается самый большой общий делитель всех элементов.

После этого каждый элемент массива делится на найденный НОД, то есть последовательность сокращается.

Например, для последовательности:

3 6 9 12 18

общий НОД равен 3. После сокращения получаем:

1 2 3 4 6