НОД последовательности из 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.

Новые блоги и статьи Все статьи Все блоги /
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .

@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

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

Решение

Решение

Решение