НОД последовательности из N чисел

@Nick Prudnykov · Регистрация: 13.09.2022

Студворк — интернет-сервис помощи студентам

Здравствуйте! Прошу помощи в исправлении кода.

Заранее буду очень благодарен.

Задача 10 - НОД последовательности из N чисел
Ограничение по времени: 0.2 секунды
Ограничение по памяти: 64 мегабайта

Задана последовательность из N целых чисел. Напишите программу, которая находит наибольший общий делитель всех элементов этой последовательности.

Формат входных данных
В первой строке входных данных записано число N (1 ≤ N ≤ 5000). Далее следует N чисел, каждое из которых не превосходит
10^9 по абсолютной величине.

Формат выходных данных
Выведите наибольший общий делитель всех элементов заданной последовательности.

Примеры

Тест Ответ
4 1
5 6 0 3

5 8
24 3600 48 0 56

4
199 199 -199 -199 199

Вот код к задаче:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return (a == 0) ? b: gcd(b % a, a);
}
 
int main() {
    int n, m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        m = gcd(m, a);
    }
    cout << m;
    return 0;
}

Тест Результат: Баллы Время Память
1 OK 4,80 0,002 256,0k
2 OK 4,80 0,002 256,0k
3 OK 4,80 0,002 264,0k
4 OK 4,80 0,001 256,0k
5 OK 4,80 0,002 256,0k
6 OK 4,80 0,002 256,0k
7 OK 4,80 0,003 256,0k
8 OK 4,80 0,003 256,0k
9 WA 0 0,003 256,0k
10 OK 4,80 0,003 256,0k
11 OK 4,80 0,006 260,0k
12 WA 0 0,008 308,0k
13 WA 0 0,005 256,0k
14 WA 0 0,004 256,0k
15 OK 4,80 0,003 256,0k
16 OK 4,80 0,009 256,0k
17 OK 4,80 0,003 256,0k
18 WA 0 0,004 256,0k
19 OK 4,80 0,004 252,0k
20 OK 4,80 0,004 256,0k

Прошу вашей помощи

@anton78spb · 19.09.2022, 12:00

Nick Prudnykov,

Python
1
2
3
4
5
6
7
from math import gcd
from functools import reduce
 
n = int(input())
d = list(map(int, input().split()))
 
print(reduce(gcd, d))

Code
1
2
3
4
5
6
7
5
24 3600 48 0 56
8
 
 
** Process exited - Return Code: 0 **
Press Enter to exit terminal

@Nick Prudnykov · 19.09.2022, 12:24 **[ТС]**

Здравствуйте, вчера закинул очень похожий код на Ваш и не прошло все проверки. А сейчас проверил Ваш код и тоже зашел на 0.
Ваш код:

Python
1
2
3
4
5
6
7
#include <iostream>
#include <math.h>
from functools import reduce
n = int(input())
d = list(map(int, input().split()))
 
print(reduce(gcd, d))

1 WA 0 0,001 3 260,0k
2 WA 0 0,000 3 172,0k
3 WA 0 0,000 3 188,0k
4 WA 0 0,001 3 184,0k
5 WA 0 0,000 3 196,0k
6 WA 0 0,000 3 204,0k
7 WA 0 0,001 3 248,0k
8 WA 0 0,000 3 232,0k
9 WA 0 0,001 3 240,0k
10 WA 0 0,001 3 228,0k
11 WA 0 0,000 3 240,0k
12 WA 0 0,001 3 260,0k
13 WA 0 0,001 3 220,0k
14 WA 0 0,002 3 280,0k
15 WA 0 0,001 3 248,0k
16 WA 0 0,002 3 224,0k
17 WA 0 0,002 3 288,0k
18 WA 0 0,001 3 208,0k
19 WA 0 0,002 3 248,0k
20 WA 0 0,002 3 208,0k

Не могу даже предположить с чем это может быть связано, но все равно большое спасибо Вам)

@anton78spb · 19.09.2022, 12:40

Сообщение от Nick Prudnykov

Здравствуйте, вчера закинул очень похожий код на Ваш и не прошло все проверки. А сейчас проверил Ваш код и тоже зашел на 0.

Очень странно. Т.к. все контрольные задания из вашего топика он выполняет.
Вы уверены что закинули мой код? Т.к. приложили вы какую-то смесь из С++ с моим кодом.

Сообщение от Nick Prudnykov

#include <iostream>
#include <math.h>
from functools import reduce
n = int(input())
d = list(map(int, input().split()))
print(reduce(gcd, d))

Добавлено через 1 минуту
Еще раз приложу код.

Python
1
2
3
4
5
6
7
from math import gcd
from functools import reduce
 
n = int(input())
d = list(map(int, input().split()))
 
print(reduce(gcd, d))

@Nick Prudnykov · 19.09.2022, 13:11 **[ТС]**

Вот, я прикрепил фото. Прошу прощение, закинул Ваш код, а потом ответил на ваше сообщение уже с другим кодом. На прикрепленных 2 фото Ваш код и ошибки, возможно Система оценки хромает, не видит что-то по каким-то причинам.

@Nick Prudnykov · 19.09.2022, 13:16 **[ТС]**

Я напишу преподавателю, скорее всего дело в системе проверки. Огромное вам спасибо, главное, что Ваш код работает, а все остальное пустяки)

Yuri V · 19.09.2022, 13:26

Формально выдаёт правильный результат и проходит требования (0,2с и 64МБ), а если глянуть "подробицы" ?

@Nick Prudnykov · 19.09.2022, 13:30 **[ТС]**

На втором фото, там где вывод ошибок это и есть подробности, но есть объяснение ошибок.
Вердикт Опис вердикту

OK
Accepted. Рішення успішно відпрацювало на вказаному тесті. Якщо такий вердикт отримано на всіх тестах, це означає, що ви повністю вирішили завдання.

CE
Compilation Error. Помилка компіляції. Компілятор не створив файл, що виконується. Вам надається повне виведення компілятора. Можливі причини: синтаксична помилка в програмі, при відправці була вказана неправильна мова програмування.

PE
Presentation Error. Неправильний формат виводу. На вказаному тесті програма виводить дані, які не відповідають умові завдання. Можливі причини: програма виводить у вихідні дані сторонній текст; програма виводить недостатню кількість вихідних даних; використовується файлове введення/виведення і вихідний файл вказаний у програмі неправильно; вихідні дані взагалі створюються.

WA
Wrong Answer. На цьому тесті ваше рішення видає неправильну відповідь. Можливі причини: реалізований неправильний алгоритм, відбулося переповнення в цілісній змінній, речові значення виводяться з недостатньою точністю.

TL
Time Limit Exceeded. На цьому тесті перевищено час виконання програми, тобто. ваша програма працює довше, ніж допустимо для цього завдання. Можливі причини: алгоритм через помилку входить до безкінечного циклу; написаний алгоритм розв'язання задачі має неправильну асимптотику, тобто є неоптимальним та його треба спробувати покращити.

ML
Memory Limit Exceeded. На зазначеному тесті перевищено огранічні пам'яті, тобто. Ваша програма вимагає більше оперативної пам'яті, ніж допустимо для цього завдання. Можливі причини: алгоритм використовує великі структури даних; в алгоритмі відбувається дуже багато рекурсивних викликів.

RE
Runtime Error. На вказаному тесті програма неправильно завершила роботу, іншими словами, сталася помилка під час виконання програми. Можливі причини: розподіл на нуль, вилучення кореня квадратного з негативного числа, звернення до неіснуючих елементів масиву чи рядка тощо.

FF
Forbiden Function. Заборонена функція. На вказаному тесті програма викликала одну з функцій, яка може порушити роботу системи тестування.

@anton78spb · 19.09.2022, 13:58

Nick Prudnykov, Вот вам еще код на "плюсах" (С++ 14).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    int d[n];
    for (int i = 0; i < n; i++)
        cin >> d[i];
    int result = d[0];
    for (int i = 1; i < n; i++)
        result = __gcd(result, d[i]);
    cout << abs(result);
}

@Nick Prudnykov · 19.09.2022, 14:03 **[ТС]**

Я понял в чем заключается ошибка, Дотс система принимает входные данные не так:

4
5 6 0 3

а так

4 5 6 0 3

И нужно 1 элемент как-то игнорировать

А что касается Вашего последнего кода, то он работает, ошибок нет!

Спасибо Вам большое за помощь, я очень рад, что нашелся такой человек, как Вы

@anton78spb · 19.09.2022, 14:50

Сообщение от Nick Prudnykov

И нужно 1 элемент как-то игнорировать

Python
1
2
3
4
from math import gcd
from functools import reduce
 
print(reduce(gcd, list(map(int, input().split()))[1:]))

Можете проверить, если еще есть необходимость.

Сообщение от Nick Prudnykov

Спасибо Вам большое за помощь, я очень рад, что нашелся такой человек, как Вы

Рад был помочь. Тут много хороших, грамотных и добрых людей.

@Kivik · 24.06.2024, 11:23

Вот код на С++ без использования функция, "делающих это за нас".

C++
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
 
using namespace std;
 
bool isDivisor(vector<int> &A, int d)
{
    for (int i : A){
        if (i % d != 0){
            return false;
        }
    }
    return true;
}
 
void reduction(vector<int> &A)
{
    int div, minn = A[0];
    for (int i : A){
        if (i < minn){
            minn = i;
        }
    }
    for (int i = minn; i > 0; --i){
        if (isDivisor(A, i)){
            div = i;
            break;
        }
    }
    for (int i = 0; i < A.size(); ++i){
        A[i] /= div;
    }
 
}
 
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 < A.size(); ++i){
        cout << A[i] << " ";
    }
    return 0;
}

@TheCalligrapher · 24.06.2024, 20:29

Сообщение от Kivik

Вот код на С++ без использования функция, "делающих это за нас".

Что это и к чему это? И как вообще могло прийти в голову вытворять вот такую феерию

C++
29
30
for (int i = minn; i > 0; --i){
        if (isDivisor(A, i)){

Причем ненужная тормозня - это гигантская проблема, но все таки помимо нее: что здесь произойдет при отрицательном входе? И это в то время как совершенно правильный и эффективный подход уже продемонстрирован в исходном вопросе.

Ошибка исходного решения ТС заключается лишь в том, что ТС забыл сделать правильную обработку для отрицательных чисел.

---

Отдельный вопрос: какое отношение этот код вообще имеет к исходной задаче? Вывод не соответствует требованиям даже отдаленно.

Добавлено через 2 минуты

Сообщение от anton78spb

Вот вам еще код на "плюсах" (С++ 14).

Если это "код на "плюсах" (С++ 14)", то что здесь делает некая странная функция __gcd? Функция для вычисления НОД в С++14 называется std::gcd.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

НОД последовательности из N чисел

Решение

Решение

Решение

@Nick Prudnykov 1 / 1 / 0 Регистрация: 13.09.2022 Сообщений: 21
	19.09.2022, 13:11 [ТС]
	Вот, я прикрепил фото. Прошу прощение, закинул Ваш код, а потом ответил на ваше сообщение уже с другим кодом. На прикрепленных 2 фото Ваш код и ошибки, возможно Система оценки хромает, не видит что-то по каким-то причинам. Миниатюры 0

@Nick Prudnykov 1 / 1 / 0 Регистрация: 13.09.2022 Сообщений: 21
	19.09.2022, 13:16 [ТС]
	Я напишу преподавателю, скорее всего дело в системе проверки. Огромное вам спасибо, главное, что Ваш код работает, а все остальное пустяки) 0

Yuri V 259 / 205 / 60 Регистрация: 25.05.2022 Сообщений: 879
	19.09.2022, 13:26
	Формально выдаёт правильный результат и проходит требования (0,2с и 64МБ), а если глянуть "подробицы" ? 0

@Nick Prudnykov 1 / 1 / 0 Регистрация: 13.09.2022 Сообщений: 21
	19.09.2022, 13:30 [ТС]
	На втором фото, там где вывод ошибок это и есть подробности, но есть объяснение ошибок. Вердикт Опис вердикту OK Accepted. Рішення успішно відпрацювало на вказаному тесті. Якщо такий вердикт отримано на всіх тестах, це означає, що ви повністю вирішили завдання. CE Compilation Error. Помилка компіляції. Компілятор не створив файл, що виконується. Вам надається повне виведення компілятора. Можливі причини: синтаксична помилка в програмі, при відправці була вказана неправильна мова програмування. PE Presentation Error. Неправильний формат виводу. На вказаному тесті програма виводить дані, які не відповідають умові завдання. Можливі причини: програма виводить у вихідні дані сторонній текст; програма виводить недостатню кількість вихідних даних; використовується файлове введення/виведення і вихідний файл вказаний у програмі неправильно; вихідні дані взагалі створюються. WA Wrong Answer. На цьому тесті ваше рішення видає неправильну відповідь. Можливі причини: реалізований неправильний алгоритм, відбулося переповнення в цілісній змінній, речові значення виводяться з недостатньою точністю. TL Time Limit Exceeded. На цьому тесті перевищено час виконання програми, тобто. ваша програма працює довше, ніж допустимо для цього завдання. Можливі причини: алгоритм через помилку входить до безкінечного циклу; написаний алгоритм розв'язання задачі має неправильну асимптотику, тобто є неоптимальним та його треба спробувати покращити. ML Memory Limit Exceeded. На зазначеному тесті перевищено огранічні пам'яті, тобто. Ваша програма вимагає більше оперативної пам'яті, ніж допустимо для цього завдання. Можливі причини: алгоритм використовує великі структури даних; в алгоритмі відбувається дуже багато рекурсивних викликів. RE Runtime Error. На вказаному тесті програма неправильно завершила роботу, іншими словами, сталася помилка під час виконання програми. Можливі причини: розподіл на нуль, вилучення кореня квадратного з негативного числа, звернення до неіснуючих елементів масиву чи рядка тощо. FF Forbiden Function. Заборонена функція. На вказаному тесті програма викликала одну з функцій, яка може порушити роботу системи тестування. 0

@Nick Prudnykov 1 / 1 / 0 Регистрация: 13.09.2022 Сообщений: 21
	19.09.2022, 14:03 [ТС]
	Я понял в чем заключается ошибка, Дотс система принимает входные данные не так: 4 5 6 0 3 а так 4 5 6 0 3 И нужно 1 элемент как-то игнорировать А что касается Вашего последнего кода, то он работает, ошибок нет! Спасибо Вам большое за помощь, я очень рад, что нашелся такой человек, как Вы 0