10814. Упрощение дробей

Написать программу, которая сокращает заданную дробь.

Вход. Первая строка содержит количество тестов n (n £ 20). Каждая из следующих n строк содержит дробь в виде p / q (1 £ p, q £ 10³⁰).

Выход. Для каждого теста вывести дробь после сокращения.

Пример входа

4

1 / 2

2 / 4

3 / 3

4 / 2

Пример выхода

1 / 2

1 / 2

1 / 1

2 / 1

РЕШЕНИЕ

длинная арифметика

Анализ алгоритма

Поскольку входные числа не более 10³⁰, то следует использовать класс длинной арифметики BigInteger. Для сокращения дроби p / q следует найти d = НОД(p, q) и разделить числитель и знаменатель дроби на d.

Реализация алгоритма

Для вычисления наибольшего общего делителя двух длинных чисел функция GCD использует константу 0, занесенную в переменную Zero.

BigInteger Zero(0);

BigInteger GCD(BigInteger a, BigInteger b)

{

if (b > Zero) return GCD(b,a.mod(b));

return a;

}

Читаем количество тестов tests. Заносим числитель и знаменатель дроби в переменные p и q типа BigInteger.

scanf("%d",&tests);

for(i=0;i<tests;i++)

{

scanf("%s",s); p = BigInteger(string(s)); scanf("%s",s);

scanf("%s",s); q = BigInteger(string(s));

d = GCD(p,q);

p = p / d; q = q / d;

p.print();printf(" / "); q.print();printf("\n");

}