e-olymp 137. НОД

25/12/2018 by Михаил Бутник

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 15 25	5
2	3 99 358 2	1
3	5 81 99 72 108 36	9
4	2 25 50	25
5	4 132 36 66 18	6

Код

#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;
}

#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;

}

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

Запустить код (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 571. НОД

27/12/2017 by Яна Колчинская

Задача

Найти НОД (наибольший общий делитель ) $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

Код

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    while (a!=0 && b!=0) {
        if (a>b) {
            a=a%b;
        }
        else b=b%a;
    }
    return a+b;
}

int main () {
    int t, a, b;
    cin>>t>>b;
    for (int i=2; i<=t; ++i) {
        cin>>a;
        b=gcd (a, b);
    }
    cout<<b;
    return 0;
}

#include <iostream>

using namespace std;

int gcd (int a, int b) {

while (a!=0 && b!=0) {

if (a>b) {

a=a%b;

}

else b=b%a;

}

return a+b;

}

int main () {

int t, a, b;

cin>>t>>b;

for (int i=2; i<=t; ++i) {

cin>>a;

b=gcd (a, b);

}

cout<<b;

return 0;

}

Решение задачи

Для решения данной задачи воспользуемся алгоритмом Евклида — алгоритмом нахождения наибольшего общего делителя (НОД) пары целых чисел, т.е. самого большого числа, на которое можно без остатка разделить оба числа, для которых ищется НОД.

Условие задачи на e-olymp
Код решения на ideone

Related Images:

A333. Наибольший общий делитель чисел последовательности

29/11/2016 by Вадим Гордийчук

Примечание: [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

Код программы

#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;
}

#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;

}

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);
    }
}

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], который и является ответом.

Ссылки

Related Images:

e-olymp 4482. В стране невыученных уроков 2

27/06/2016 by Алина Гончарова

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

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

Первая строка содержит количество элементов в массивеn (1 ≤ n ≤ 10⁶). Во второй строке находится n чисел – элементы a_i (1 ≤ a_i ≤ 10⁹) массива. В третьей строке находится количество запросовm (1 ≤ m ≤ 10⁵). Далее в m строках находится по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int equality(int a, int b){
    return a == b ? a : 0;
}
 
void build(int *a, int *tr, int v, int l, int r) {
    if (l == r) {
        tr[v] = a[l];
    } else {
        int middle = (l + r) / 2;
        build(a, tr, 2 * v, l, middle);
        build(a, tr, 2 * v + 1, middle + 1, r);
        tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
    }
}
 
void update(int *tr, int v, int l, int r, int pos, int val) {
    if (l == r) {
        tr[v] = val;
    } else {
        int middle = (l + r) / 2;
        if (pos <= middle) {
            update(tr, 2 * v, l, middle, pos, val);
        } else {
            update(tr, 2 * v + 1, middle + 1, r, pos, val);
        }
        tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
    }
}
 
int getEquality(int *tr, int v, int l, int r, int left, int right) {
    if (l == left && r == right) {
        return tr[v];
    }
    int middle = (l + r) / 2;
    if (right <= middle) {
        return getEquality(tr, 2 * v, l, middle, left, right);
    }
    else if (left >= middle + 1) {
        return getEquality(tr, 2 * v + 1, middle + 1, r, left, right);
    }
    else {
        return equality(getEquality(tr, 2 * v, l, middle, left, middle), 
            getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right));
    }
}
 
int main() {
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int *tr = new int[4 * n];
    build(a, tr, 1, 0, n - 1);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int q, l, r;
        cin >> q >> l >> r;
        if (q == 1) {
            cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl;
        } else if (q == 2) {
            update(tr, 1, 0, n - 1, l - 1, r);
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int equality(int a, int b){

return a == b ? a : 0;

}

void build(int *a, int *tr, int v, int l, int r) {

if (l == r) {

tr[v] = a[l];

} else {

int middle = (l + r) / 2;

build(a, tr, 2 * v, l, middle);

build(a, tr, 2 * v + 1, middle + 1, r);

tr[v] = equality(tr[2 * v], tr[2 * v + 1]);

}

void update(int *tr, int v, int l, int r, int pos, int val) {

if (l == r) {

tr[v] = val;

} else {

int middle = (l + r) / 2;

if (pos <= middle) {

update(tr, 2 * v, l, middle, pos, val);

} else {

update(tr, 2 * v + 1, middle + 1, r, pos, val);

}

tr[v] = equality(tr[2 * v], tr[2 * v + 1]);

}

int getEquality(int *tr, int v, int l, int r, int left, int right) {

if (l == left && r == right) {

return tr[v];

}

int middle = (l + r) / 2;

if (right <= middle) {

return getEquality(tr, 2 * v, l, middle, left, right);

}

else if (left >= middle + 1) {

return getEquality(tr, 2 * v + 1, middle + 1, r, left, right);

}

else {

return equality(getEquality(tr, 2 * v, l, middle, left, middle),

getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right));

}

int main() {

int n;

cin >> n;

int *a = new int[n];

for (int i = 0; i < n; i++) {

cin >> a[i];

}

int *tr = new int[4 * n];

build(a, tr, 1, 0, n - 1);

int m;

cin >> m;

for (int i = 0; i < m; i++) {

int q, l, r;

cin >> q >> l >> r;

if (q == 1) {

cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl;

} else if (q == 2) {

update(tr, 1, 0, n - 1, l - 1, r);

}

return 0;

}

Тесты

Входные данные	Выходные данные
5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 1	wins wins wins draw
5 7 7 7 7 7 4 1 1 5 2 2 1 1 1 5 1 3 5	draw wins draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.

Related Images:

e-olymp 4481. В стране невыученных уроков

27/06/2016 by Катя Писова

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные:	Выходные данные:
5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 5	2 2 5 1

Код программы

#include <iostream>
#include <vector>
using namespace std;

vector<int> tree;
int n;

int gcd (int a, int b){
    if (a == 0) return b;
   return gcd(b % a, a);
}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = a[tl];
    }else{
        int middle = (tl + tr) / 2;
        build(a, v * 2, tl, middle);
        build(a, v * 2 + 1, middle + 1, tr);
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){
    if(l > r){
        return 0;
    }
    if(tl == l && tr == r){
        return tree[v];
    }
    int middle = (tl + tr) / 2;
    int L = get(a, l, min(middle, r), v * 2, tl, middle);
    int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);
    return gcd(L, R);

}
void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = val;
    }else{
        int middle = (tl + tr) / 2;
        if(pos <= middle){
            update(pos, val, v * 2, tl, middle);
        }else{
            update(pos, val, v * 2 + 1, middle + 1, tr);
        }
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int main(){
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    tree.resize(4 * n);
    build(a);
    int m, l, r, q; 
    cin >> m;
    while (m--){
        cin >> q >> l >> r;
        if (q == 1){
            cout << get(a, l - 1, r - 1) << endl;
        }
        else{
            update(l - 1, r);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> tree;

int n;

int gcd (int a, int b){

if (a == 0) return b;

return gcd(b % a, a);

}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = a[tl];

}else{

int middle = (tl + tr) / 2;

build(a, v * 2, tl, middle);

build(a, v * 2 + 1, middle + 1, tr);

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){

if(l > r){

return 0;

}

if(tl == l && tr == r){

return tree[v];

}

int middle = (tl + tr) / 2;

int L = get(a, l, min(middle, r), v * 2, tl, middle);

int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);

return gcd(L, R);

}

void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = val;

}else{

int middle = (tl + tr) / 2;

if(pos <= middle){

update(pos, val, v * 2, tl, middle);

}else{

update(pos, val, v * 2 + 1, middle + 1, tr);

}

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int main(){

cin >> n;

int a[n];

for (int i = 0; i < n; i++){

cin >> a[i];

}

tree.resize(4 * n);

build(a);

int m, l, r, q;

cin >> m;

while (m--){

cin >> q >> l >> r;

if (q == 1){

cout << get(a, l - 1, r - 1) << endl;

}

else{

update(l - 1, r);

}

return 0;

}

Алгоритм решения

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение НОД на отрезке и запрос на модификацию элемента являются рекурсивными. Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

В самой задаче, в зависимости от требуемого, в цикле находим НОД на заданном отрезке или выполняем модификацию элемента.

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 1154. Кружок хорового пения.

30/09/2015 by Радик Сиденко

Условие задачи:

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex], где [latex]\left( 1 \le N, M \le {10}^{3} \right).[/latex]

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

Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».

Тесты:

n	m	answer
4	1	YES
6	3	NO

Решение:

Для начала нам надо найти наибольший общий делитель(НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице то все ученики распоются и мы выводим «YES» в другом случае мы выводим «NO».

Код:

#include <iostream> 
using namespace std; 
int main() { 
    int n, m, p; 
    while(cin >> n >> m) {
        if (m > n) { 
            p = n; 
            n = m; 
            m = p; 
        } 
        while (m > 0) { 
            p = n % m; 
            if (p != 0) {
                n = m; 
                m = p; 
            } 
            else break; 
        } 
        cout<<(m==1?"YES": "NO")<<endl;
    } 
    return 0; 
}