e-olymp 8367. Таксі

Задача

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

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

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

Завдання

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

Вхідні дані

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

Вихідні дані

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

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

Оцінювання

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

  1. $0$ Тести з умови —
  2. $41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
  3. $33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
  4. $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)

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

 

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

Спочатку зазначимо, що для рейтингу з точністю $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)

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

Задача

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

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

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

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

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

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

Тесты

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

Continue reading

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

Задача

Дробь $\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

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

Решение

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

Ссылки

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

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $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

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

Решение

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

  1. $a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
  2. Существует такое $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$ — количество кратных элементов последовательности.
  3. Не существует такого $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.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

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

Задача


Биллиард представляет собой прямоугольник размерами $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

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

Решение

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

Ссылки

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

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

Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [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

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

Пусть у нас есть [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

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

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [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$

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

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

Согласно свойству НОД, если некоторые числа [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
Код решения

e-olymp 571. НОД

Задача

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

Код

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


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

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

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

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

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

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

Для решения данной задачи необходимо использовать данную в условии формулу [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], который и является ответом.

Ссылки

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

Задача

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

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

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

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

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

Решение

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

Код

Тесты

Входные данные Выходные данные
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.

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