e-olymp 7239. «Все, Степан! Ти мене дістав!»

23/12/2020 by Жук Світлана

Задача

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок «три — чотири» хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час $t_1$, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робить те ж саме за час $t_2$.

Весь цей час викладач настільки захоплений доведенням теореми, що взагалі нічого не чує. І тільки коли обидві бульбашки лопнуть одночасно, викладач почує шум і обернеться. І тоді вже точно студентам попаде на горіхи, а більше усього тому, хто приніс на пару жувальні гумки.

Визначте, скільки часу хлопці можуть насолоджуватись надуванням бульбашок, не замічені викладачем.

Наприклад, якщо $t_1 = 2$, $t_2 = 3$, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу $t = 0$ до моменту часу $t = 2$, потім бульбашка лопається, і він надуває бульбашку знову — з моменту часу $t = 2$ до моменту часу $t = 4$, а потім ще раз — з моменту часу $t = 4$ до $t = 6$.

Товариш Степана надуває бульбашку з $t = 0$ до $t = 3$ і ще раз з $t = 3$ до $t = 6$.

В момент часу $t = 6$ бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: «Все, Степан! Ти мене дістав!».

Формат вхідних даних

Перший рядок вхідного файлу містить два цілих числа $t_1, t_2 (1 \leqslant t_1, t_2 \leqslant 10^9).$

Формат вихідних даних

Вихідний файл повинен містити одне ціле число — час, протягом якого Степан з товаришем можуть насолоджуватись надуванням бульбашок.

Тести

№	Вхідні дані	Вихідні дані
1	2 3	6
2	1 16	16
3	10 10	10
4	100000000 150000000	300000000
5	17 41	697

Код

#include <iostream>

using namespace std;
 
long nod (int a, int b)  {
    return b == 0 ? a : nod (b, a % b);
}
 
int main() {
    int t1, t2;
    cin >> t1 >> t2;
    cout <<  t1 * (t2 / nod (t1, t2));
    return 0;
}

#include <iostream>

using namespace std;

long nod (int a, int b) {

return b == 0 ? a : nod (b, a % b);

}

int main() {

int t1, t2;

cin >> t1 >> t2;

cout << t1 * (t2 / nod (t1, t2));

return 0;

}

Розв’язання

алгоритмом Евкліда,

Посилання

Задача на e-olymp
Код на ideone
Зараховане розв’язання на e-olymp

Related Images:

e-olymp 6941. Сумма НОД

22/12/2020 by Натан Чачко

Задача

Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

Тесты

№	Входные данные	Выходные данные
1	3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35
2	2 3 12 7 8 4 5 14 25 11	6 10
3	4 4 5 6 7 8 4 8 6 2 9 3 2 15 6 5 12 25 29 19 11	7 11 6 10

Код

#include <iostream>
using namespace std;

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

int main() {
    int n, m, sum;
    cin >> n;
    while(n-- > 0) {
        cin >> m; 
        int ns[m];
        for(int i = 0; i < m; i++) cin >> ns[i];
        sum = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);
        }
        cout << sum << endl;
    }
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a%b);

}

int main() {

int n, m, sum;

cin >> n;

while(n-- > 0) {

cin >> m;

int ns[m];

for(int i = 0; i < m; i++) cin >> ns[i];

sum = 0;

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

for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);

}

cout << sum << endl;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 1602. НОК двух натуральных чисел

22/12/2020 by Федяєва Євгенія

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

№	Входные данные	Выходные данные
1	42 24	168
2	32 14	224
3	101 45	4545

Код

#include <iostream>
using namespace std;
 
long int GCD(int num1, int num2) 
{
    if(num1 == num2) return num1;
    while(num1 && num2)
    {
        if(num1 > num2) num1 %= num2;
        else num2 %= num1;
    }
    return num1+num2;
}
 
int main() {
    long int num1, num2, gcd;
    cin >> num1 >> num2;
    gcd = GCD(num1, num2);
    cout << num1*num2/gcd;
    return 0;
}

#include <iostream>

using namespace std;

long int GCD(int num1, int num2)

{

if(num1 == num2) return num1;

while(num1 && num2)

{

if(num1 > num2) num1 %= num2;

else num2 %= num1;

}

return num1+num2;

}

int main() {

long int num1, num2, gcd;

cin >> num1 >> num2;

gcd = GCD(num1, num2);

cout << num1*num2/gcd;

return 0;

}

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 8367. Таксі

17/06/2019 by Таисия Ткачева

Задача

Аліна хоче замовити таксі через один відомий додаток. Одразу декілька водіїв готові приїхати на її замовлення.

Проте Аліна — дівчинка відповідальна, вона бажає поїхати із найдосвідченішим таксистом, тобто з тим, який вже здійснив найбільшу кількість перевезень. Але ось невдача — додаток не показує кількість перевезень, здійснених водієм. Єдина інформація, якою володіє Аліна — рейтинг водія.

Нагадаємо, що по завершенню кожного перевезення пасажир виставляє водієві оцінку — ціле число від $1$ до $5$ включно. Рейтинг таксиста $R$ рахується як середнє арифметичне усіх отриманих ним оцінок.

Завдання

Допоможіть Аліні – напишіть програму, яка визначить мінімально можливу кількість перевезень, які мав здійснити таксист щоб отримати рейтинг рівно $R$ (без округлень).

Вхідні дані

В єдиному рядку вхідного файлу знаходиться дійсне число $R$ $\left(1 \leqslant R \leqslant 5 \right)$ — рейтинг водія з точністю не більш ніж $18$ знаків після десяткової крапки.

Вихідні дані

В першому рядку вихідного файлу виведіть єдине натуральне число — відповідь на задачу, або $-1,$ якщо заданий рейтинг отримати неможливо.

Якщо рейтинг отримати можливо, у другому рядку необхідно вивести $5$ цілих невід’ємних чисел — кількість оцінок $1,$ $2,$ $3,$ $4$ і $5$ відповідно, отриманих водієм. У разі коли існує декілька варіантів оцінок, які призводять до оптимальної відповіді, дозволяється вивести будь-який з них.

Оцінювання

Пiдзадача. Бали. Додатковi обмеження. Необхідні підзадачі.

$0$ Тести з умови —
$41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
$33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
$26$ Точнiсть $R$ не бiльш нiж $18$ знаків пiсля коми $0,$ $1,$ $2$

Тести

#	Вхідні дані	Вихідні дані
1	3.0009	10000 0 0 9991 9 0
2	2.0805216	312500 0 287337 25163 0 0
3	4.999999999999999998	500000000000000000 0 0 0 1 499999999999999999
4	1.123581321345589144	125000000000000000 109552334831801357 15447665168198643 0 0 0
5	3.141592653585793236	250000000000000000 0 0 214601836603551691 35398163396448309 0

Код (cтроки string)

#include <iostream>
#include <string> 
using namespace std;
 
unsigned long long GCD (unsigned long long a, unsigned long long b) {
    while (b) {
        a %= b;
        swap (a, b);
    }
    return a;
}
 
int main() {
    string str;
    cin >> str;
    int length = str.length();
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD (numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if (i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if (fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <string>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

while (b) {

a %= b;

swap (a, b);

}

return a;

}

int main() {

string str;

cin >> str;

int length = str.length();

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

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

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD (numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

for (int i = 1; i <= 5; i++) {

if (i == fraction) {

i++;

cout << denominator - remainder << " ";

if (fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

Код (cтроки c-string)

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

unsigned long long GCD (unsigned long long a, unsigned long long b) {
    if (b == 0) return a;
    else return GCD (b, a % b);
}

int main() {
    char str[20];
    int length = 0;
    while (cin >> str[length]) length++;
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD(numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if(i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if(fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

if (b == 0) return a;

else return GCD (b, a % b);

}

int main() {

char str[20];

int length = 0;

while (cin >> str[length]) length++;

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

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

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD(numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

for (int i = 1; i <= 5; i++) {

if(i == fraction) {

i++;

cout << denominator - remainder << " ";

if(fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

Розв’язок задачі

Спочатку зазначимо, що для рейтингу з точністю $k$ знаків після десяткової коми оптимальна відповідь завжди $\leqslant 10^k$. Розглянемо це на прикладі. Нехай ми маємо рейтинг $3.xxx,$ де $xxx$ — $3$ будь-які цифри. Припустимо, що таксист отримав $10^3=1000$ оцінок $3.$ Тоді його рейтинг буде дорівнювати $\frac{3\cdot1000}{1000}=3.000,$ тобто рівно $3.$ Тепер спробуємо замінити одну оцінку $3$ на $4.$ Тоді його рейтинг дорівнюватиме $\frac{3\cdot 999+4\cdot 1}{999+1}=\frac{3001}{1000}.$ Тобто замінивши одну трійку на четвірку ми збільшили рейтинг на $\frac{1}{1000}.$ Таким чином якщо поступово змінювати усі $3$ на $4$ ми зможемо отримати будь-який рейтинг від $3.000$ до $4.000$ з трьома знаками після коми, а отже і заданий рейтинг $3.xxx.$

Підзадача $1$:

Виходячи з вищезазначеного відповідь $\leqslant 10.$ Тоді ЇЇ можна отримати просто перебравши усі можливі комбінації оцінок $5$-ма вкладеними циклами.

Підзадача $2$:

Доведемо, що оптимальну відповідь завжди можна отримати тільки за допомогою оцінок двох сусідніх типів $a$ та $\left(a+1\right),$ або одного типу (якщо рейтинг цілий). Припустимо, що існує оптимальна відповідь, у якій НЕ сусідні оцінки $x$ та $y,$ $x<y.$ У випадку, якщо $y-x=3,$ ми можемо замінити їх на $x+1$ та $y-1.$ Якщо $y-x=2$ або $y-x=4,$ можна замінити їх на дві оцінки по $x+1$ або $x+2$ відповідно. Ці дії жодним чином не впливають ні на суму, ні на кількість оцінок, а тому не впливають і на середнє арифметичне. Таким чином, будь-який набір оцінок можна звести до набору оцінок з щонайбільше двох типів. Очевидно, що ці два типи — рейтинг округлений вниз та вгору.

Тоді розв’язання полягає у тому щоб перебрати кількість оцінок першого типу, порахувати скільки потрібно оцінок другого типу, аби отримати заданий рейтинг і перевірити, чи кількість оцінок другого типу ціла (тобто такий розподіл оцінок можливий). Нехай рейтинг рівня $R,$ покладемо $a=\lfloor R\rfloor,$ кількість оцінок типу $a$ дорівнює $x,$ а кількість оцінок типу $a+1$ (якщо вони необхідні) дорівнює $y.$ Тоді, $x\cdot a+y\cdot\left(a+1\right)=R\cdot x+R\cdot y.$ З цього, щоб отримати точну відповідь, потрібно виконувати операції у цілих числах або у $64$-бітних числах з плавоючою комою.

Підзадача $3$:

Представимо рейтинг $R$ у вигляді звичайного дробу, домноживши чисельник та знаменник на $10^{18}$. Виходячи з визначення середнього арифметичного, знаменник цього дробу $10^{18}$ — кількість отриманих оцінок, а чисельник $\left( R \cdot 10^{18} \right)$ — їх сума. Якщо цей дріб можна скоротити, це зменшить кількість оцінок, тому що знаменник (тобто кількість оцінок) зменшиться, а відношення чисельника до знаменника (тобто рейтинг) не зміниться. Отже, чисельник і знаменник потрібно поділити на їх НСД. Припустимо, що після скорочення ми отримали дріб $\frac{a}{b}.$ Очевидно, що отримане у знаменнику число $\left( b \right)$ і є оптимальною відповіддю, адже дріб нескоротний і зменшити знаменник не вдасться. Тепер потрібно довести, що ця відповідь завжди досяжна, тобто існує набір з $b$ оцінок від $1$ до $5$, сума яких дорівнює $a.$

Доведення цього факту аналогічне доведенню у підзадачі $2.$ Зауважимо, що завжди $b \leqslant a \leqslant 5b,$ бо рейтинг за умовою від $1$ до $5$. Тепер припустимо, що усі оцінки дорівнюють $1.$ Тоді чисельник дорівнюватиме $1 \cdot b,$ тобто $b.$ Тепер змінемо будь-яку оцінку $\left( m \neq 5 \right)$ на $m+1.$ Тоді чисельник збільшиться на $1,$ а знаменник залишиться рівним $b.$ Поступово здійснюючи такі заміни, можемо припустити «пройти» через усі значення від $b$ до $5b,$ зокрема і через $a,$ яке нам потрібно отримати.

Аби відновити самі оцінки, згадаємо доведений у другій підзадачі факт про те, що оптимальну відповідь завжди можна отримати з оцінок $\lfloor R\rfloor$ та $\lceil R\rceil.$ Якщо б усі оцінки дорівнювали $\lfloor R\rfloor,$ чисельник був би $b \cdot \lfloor R\rfloor .$ Але чисельник дорівнює $a \geqslant b \cdot \lfloor R\rfloor ,$ тому кількість оцінок $\lceil R\rceil$ як раз дорівнює залишку, тобто $a-b \cdot \lfloor R\rfloor .$ Решта оцінок – оцінки $\lfloor R\rfloor .$ Також зауважимо, що через недостатню точність зберігання чисел з плаваючою комою у пам’яті комп’ютера, необхідно зчитувати рейтинг у вигляді рядка і конвертувати одразу у ціле число.

Посилання

Умова на e-olymp
Код (cтроки string)
Код (cтроки c-string)

Related Images:

e-olymp 4752. Кинотеатр

21/05/2019 by Андрей Зиновьев

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.

Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.

Тесты

Входные данные	Вывод программы
3 3	3
3 2	2
231 543	3

Continue reading →

Related Images:

e-olymp 339. Опять несократимые

23/12/2018 by Александр Мога

Задача

Дробь $\frac{m}{n}\ $ называется правильной несократимой, если [latex] 0 < m < n [/latex] и [latex] НОД (m, n) = 1.[/latex] Найдите количество правильных несократимых дробей со знаменателем $n$.

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

Каждая строка является отдельным тестом и содержит число $n$ ([latex]n < 10^9 [/latex]). Последняя строка содержит $0$ и не обрабатывается. Количество тестов не больше $100.$

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

Для каждого $n$ в отдельной строке вывести ответ на поставленную задачу.

Тесты

Вход	Выход
12 123456 7654321 0	4 41088 7251444
552 99693 34 991 8863 0	176 56160 16 990 8862
1 5754 99291 7752 3321 0	1 1632 63272 2304 2160
99291 581293 3215788 1224262 68291 692110 0	63272 581292 1422720 565032 66792 272448
3 12 64 877 0	2 4 32 876

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

#include <iostream>
using namespace std;

int main () {
    int n, k;
    while (cin >> n and n!=0) {
        k = n;
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n/= i;
                }
                k-=k/i;
            }
        }
        if (n > 1) {
            k-=k/n;
        }
        cout << k << endl;
    }
    return 0;   
}

#include <iostream>

using namespace std;

int main () {

int n, k;

while (cin >> n and n!=0) {

k = n;

for (int i = 2; i*i <= n; i++) {

if (n % i == 0) {

while (n % i == 0) {

n/= i;

}

k-=k/i;

}

if (n > 1) {

k-=k/n;

}

cout << k << endl;

}

return 0;

}

Решение

Вводим поток чисел до тех пор пока не встретим $0$ и проводим над каждым числом следующую операцию.
Вычисляем количество правильных несократимых дробей с помощью функции Эйлера. Занимаемся проверкой числа на простоту. Простой, но медленный метод проверки простоты заданного числа $n$ известен как перебор делителей. Будем проверять, является ли $n$ кратным каждому целому числу от $2$ до $\sqrt{n}$.
В ходе проверки на простоту находим и другие кратные делители, если таковые имеются. При обнаружение какого то кратного найдем количество несократимым для данного несократимого. Частное, где числитель — это наше число, а знаменатель — определенный кратный делитель, будет количеством сократимых чисел, связанное с текущим кратным делителем. Естественно, если отнимем всё число от делимого, то получим число несократимых.
Повторяем цикл пока обнаруживаются новые кратные нашему числу и с каждым разом уменьшая количество несократимых.

Ссылки

Related Images:

e-olymp 1151. Кладоискатель

16/12/2018 by Юлиана Боурош

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

Если в конце дня ответственный преподаватель замечал, что число Роминых монет делится на $b,$ то Роме разрешалось взять с полки пирожок, который он тут же съедал. Помогите Роме посчитать, сколько пирожков он съест за время прохождения практики.

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

В выходной файл выведите число съеденных Ромой пирожков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2	1
2	2 2	2
3	10 5	5
4	56000 35	35
5	300 1000000000	100

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

#include <iostream>
using namespace std;
int GCD(int a, int b){
  if (b == 0) return a;
  else return GCD(b, a % b);
}

int main() {
  int a, b;
  cin >> a >> b;
  cout << GCD(a,b);
  return 0;
}

#include <iostream>

using namespace std;

int GCD(int a, int b){

if (b == 0) return a;

else return GCD(b, a % b);

}

int main() {

int a, b;

cin >> a >> b;

cout << GCD(a,b);

return 0;

}

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

$a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

Код на ideone.com
Задача на e-olymp.com

Related Images:

e-olymp 58. Биллиард

05/08/2018 by Александр Дьяченко

Задача

Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

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

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

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

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные	Выходные данные
2 1	1 2
5 6	9 4
12 33	13 2
156 156	0 3
654 236	443 4

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

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

int main() {
    long m, n;
    cin >> m >> n;
    long g = __gcd(m, n);
    m /= g;
    n /= g;
    cout << (n + m - 2) << " ";
    if(n % 2 == 0 and m % 2 != 0) cout << 4;
    if(n % 2 != 0 and m % 2 != 0) cout << 3;
    if(n % 2 != 0 and m % 2 == 0) cout << 2;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long m, n;

cin >> m >> n;

long g = __gcd(m, n);

m /= g;

n /= g;

cout << (n + m - 2) << " ";

if(n % 2 == 0 and m % 2 != 0) cout << 4;

if(n % 2 != 0 and m % 2 != 0) cout << 3;

if(n % 2 != 0 and m % 2 == 0) cout << 2;

return 0;

}

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

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

Related Images:

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

16/05/2018 by Андрей Святозар Чернецкий

Задача

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

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

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).

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

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

Тесты

Входные данные	Выходные данные
1000 1000 1 1	NO YES
2 5 3 7 14 15 49 37	YES YES YES YES
14 16 891 6 441 9 777 111	NO NO NO NO
4 1 6 3	YES NO

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n, m;
    while (cin >> n >> m) cout << (__gcd (n, m) == 1? "YES" : "NO") << endl;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

while (cin >> n >> m) cout << (__gcd (n, m) == 1? "YES" : "NO") << endl;

return 0;

}

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

Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется. На рисунке ниже приведен пример. [latex]6[/latex] певцов, распевается каждый [latex]2[/latex], начиная из верхнего левого угла при смене по часовой стрелке. Переливающимся кружочком обозначен поющий в данный момент певец.

Докажем, что если [latex]M[/latex] и [latex]N[/latex] взаимно просты, то все участники распоются. Для начала заметим, что при [latex]i[/latex]-ой смене (где [latex]i[/latex] некоторое натуральное число) очередь вернется к участнику, с которого распевка начиналась,то есть смена циклическая. Поскольку НОД ([latex]M, N) = 1 [/latex], то НОК ([latex]M, N) = M*N [/latex], то есть распевающий сменится [latex]N[/latex] раз для завершения цикла. Покажем, что ни один из певцов не споет более [latex]1[/latex] раза. Пусть есть некоторый [latex]k[/latex]-ый распевающий, очередь которого наступила более [latex]1[/latex] раза за время цикла. Однако, как и для первого распевающего, очередь для [latex]k[/latex] наступит через [latex]N[/latex] смен, то есть после завершения цикла. Получили опровержение. Значит каждый распоется не более [latex]1[/latex] раза. Теперь, учитывая количество смен, получим, что каждый распоется ровно [latex]1[/latex] раз. В случае, когда НОД ([latex]M, N) \geq 2 [/latex] получим, что за цикл распоется менее, чем [latex]N[/latex] участников хора.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

Related Images:

e-olymp 1128. Проблема Лонги

14/05/2018 by Алиса Ворохта

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные	Выходные данные
[latex]2[/latex] [latex]6[/latex]	$3$ $15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex]	$1$ $195$ $520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex]	$13$ $15965$ $170994915$ $4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$	$405$ $54873$ $613124817$ $1809145$ $35433480192$

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

#include <iostream>
using namespace std;
 
int main() {
    long long n, gcd, primeNumInPow, power;
    while(cin >> n)
    {
        gcd = 1;
        for(long long i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                power = 0; primeNumInPow = 1;
                while(n % i == 0) {
                    power++;
                    primeNumInPow *= i;
                    n /= i;
                }
                gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;
            }
        }       
        if (n > 1) gcd *= (2*n - 1);
        cout << gcd << endl;
    }
  return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, gcd, primeNumInPow, power;

while(cin >> n)

{

gcd = 1;

for(long long i = 2; i * i <= n; i++) {

if(n % i == 0) {

power = 0; primeNumInPow = 1;

while(n % i == 0) {

power++;

primeNumInPow *= i;

n /= i;

}

gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;

}

if (n > 1) gcd *= (2*n - 1);

cout << gcd << endl;

}

return 0;

}

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

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

Условие задачи на 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.

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