Задача
Дробь 49/98 является любопытной, поскольку неопытный математик, пытаясь сократить ее, будет ошибочно полагать, что 49/98 = 4/8, являющееся истиной, получено вычеркиванием девяток.
Дроби вида 30/50 = 3/5 будем считать тривиальными примерами.
Существует ровно 4 нетривиальных примера дробей подобного типа, которые меньше единицы и содержат двухзначные числа как в числителе, так и в знаменателе.
Пусть произведение этих четырех дробей дано в виде несократимой дроби (числитель и знаменатель дроби не имеют общих сомножителей). Найдите знаменатель этой дроби.
Решение
Тут я пошёл путём акына, а именно, что вижу, о том пою.
По условиям задачи нужно перебрать все двузначные дроби, в которых числитель меньше знаменателя. Также можно сразу не рассматривать дроби, в которых числитель или знаменатель заканчиваются на 0. Хорошо, делаем:
Что дальше? Чтобы числа теоретически сокращались, у них должна быть минимум одна общая цифра в любом разряде.
Можно написать как обычно разложение числа на разряды в цикле, но здесь достаточно прямого вычисления каждого разряда:
Далее надо найти, какие разряды в двух разных числах равны друг другу. Если они равны, то выкидываем их и оставляем остальные разряды этих чисел.
Далее надо узнать, действительно ли получается сокращение. Для этого я вычисляю дробь a * 10000 / b и сравниваю с дробью ax * 10000 / bx:
Умножаю на 10000, так как у меня целочисленная арифметика, а дроби меньше 1.
Если совпадение произошло, то обновляю текущее произведение дробей в виде отдельно числителя a_prod и отдельно знаменателя b_prod.
Найдены те самые 4 дроби, что радует:
И как можно заметить, всегда сокращается младший разряд числителя со старшим разрядом знаменателя. Так что условия проверки можно сократить, но я в этом не разбираюсь, поэтому рисковать для общего случая не буду.
В конце получилось произведение 8/800. Его надо привести к наименьшему знаменателю. Это делается банальным перебором общих множителей:
И как нетрудно догадаться, в финале получим 1/100.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: