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.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

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

  1. Юлия, первый код это тот же второй , прописывать столько if ов не рационально, советую убрать этот код и оставить второй. Задача основана на поиске НОД, так и оставьте хороший и красивый рекурсивно выполненный алгоритм Евклида(2 код) я может окажусь не прав но думаю можно найти такие числа чтоб первый код не сработал.

  2. И кроме того:
    — Списки нужно оформить тегами ol и li. Для них есть соответствующие кнопки.
    — Зачем Вы разбиваете формулы на части, вытаскивая равенство из формул. И не только.
    — То Вы делает дроби, как следует, то вдруг /. С умножением тоже самое.
    — В рассуждениях ошибки. По п.1: если $a$ кратно $b,$ то каждый день число монет будет делиться на $b.$
    — П.2 нужно сформулировать аккуратнее. Что за $k$? Возможно Вы имели в виду, что если существует такое $k$…

Добавить комментарий