2.3.5 Сложение дробей

Даны две дроби с целыми числителями и положительными знаменателями. Найдите их сумму и представьте её в виде несократимой дроби с положительным знаменателем. Если сумма равна нулю, результат должен иметь числитель 0 и знаменатель 1. Выделять целую часть не требуется.

Объявите структуру struct Fraction с полями numerator и denominator типа long long. Реализуйте функцию struct Fraction add_fractions(struct Fraction first, struct Fraction second), которая принимает две структуры по значению и возвращает структуру с сокращённой суммой. Функция не должна выполнять ввод или вывод. Для сокращения реализуйте отдельную функцию вычисления наибольшего общего делителя (НОД). При вычислении НОД учитывайте, что числитель может быть отрицательным.

В функции main прочитайте дроби, вызовите add_fractions и выведите поля возвращённой структуры. Все промежуточные вычисления выполняйте в long long: произведения знаменателей и числителей могут не помещаться в 32-битный int.

Материал к заданию

Алгоритм Евклида — Algorithmica. Используйте разбор вычисления НОД для реализации сокращения суммы дробей; в своей функции учитывайте отрицательный числитель и представление нулевого результата, заданные в условии.

Время: 2 секунды. Память: 64 МиБ. Вывод: до 2 МиБ. Стандарты: C11 / C++17.

В первой строке вводятся два целых числа p₁ и q₁ — числитель и знаменатель первой дроби. Во второй строке вводятся p₂ и q₂ — числитель и знаменатель второй дроби. Ограничения: −10⁶ ≤ p₁, p₂ ≤ 10⁶, 1 ≤ q₁, q₂ ≤ 10⁶.

Два целых числа в одной строке через пробел — числитель и знаменатель сокращённой суммы.