9426. Дроби: умножение
и деление
Даны две дроби. Найдите их произведение или частное.
Вход. В каждой строке задан пример на умножение или деление
дробей. Числитель и знаменатель каждой дроби является натуральным числом, не
большим 109.
Выход. Для каждого входного примера выведите в отдельной
строке ответ в виде несократимой дроби.
|
Пример входа |
Пример выхода |
|
2/3 * 5/6 1/2 / 4/5 7/8 * 11/41 7/1 / 3/7 |
5/9 5/8 77/328 49/3 |
РЕШЕНИЕ
математика
Анализ алгоритма
Для умножения дробей
воспользуемся формулой:
,
после чего следует сократить
дробь.
Деление на дробь эквивалентно
умножению на обратную дробь:
Реализация
алгоритма
Вычисление модуля числа.
long long abs(long long x)
{
return (x < 0) ? -x : x;
}
Вычисление наибольшего общего
делителя.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Умножение дробей a / c * b / d = u
/ v.
void mult(long long a, long long b, long long c, long long d,
long long &u, long long &v)
{
u = a * c;
v = b * d;
g = gcd(abs(u), abs(v));
u /= g; v /= g;
}
Деление дробей a / c : b / d = u
/ v.
void div(long long a, long long b, long long c, long long d,
long long &u, long long &v)
{
u = a * d;
v = b * c;
g = gcd(abs(u), abs(v));
u /= g; v /= g;
}
Основная часть программы. Читаем
входные данные. Обрабатываем запрос и выводим ответ.
while (scanf("%lld/%lld %c %lld/%lld", &a, &b, &ch,
&c, &d) == 5)
{
if (ch == '*') mult(a, b, c, d, u, v);
else div(a, b, c, d, u, v);
printf("%lld/%lld\n", u, v);
}
Java
реализация
import java.util.*;
class MyLong
{
private long a;
MyLong(long a)
{
this.a = a;
}
MyLong(Long a)
{
this.a = a;
}
MyLong Abs()
{
return new MyLong((this.a > 0) ? this.a : -this.a);
}
long GetValue()
{
return this.a;
}
private static long gcd(long a, long b)
{
if (a == 0) return b;
if (b == 0) return a;
if (a > b) return gcd(a%b,b);
return gcd(a,b%a);
}
static MyLong
gcd(MyLong a, MyLong b)
{
return new MyLong(gcd(a.Abs().GetValue(),b.Abs().GetValue()));
}
MyLong Add(MyLong a)
{
return new MyLong(this.a + a.a);
}
MyLong Sub(MyLong a)
{
return new MyLong(this.a - a.a);
}
MyLong Mult(MyLong a)
{
return new MyLong(this.a * a.a);
}
MyLong Divide(MyLong a)
{
return new MyLong(this.a / a.a);
}
public String
toString()
{
return String.valueOf(a);
}
}
class Fraction
{
MyLong numerator, denominator;
Fraction ()
{
this.numerator = new MyLong(0);
this.denominator = new MyLong(1);
}
Fraction (MyLong numerator, MyLong denominator)
{
this.numerator = numerator;
this.denominator = denominator;
}
Fraction (String s)
{
numerator = new MyLong(Long.parseLong(s.substring(0,s.indexOf('/'))));
denominator = new MyLong(Long.parseLong(s.substring(s.indexOf('/')+1)));
}
Fraction Add(Fraction a)
{
MyLong x = this.numerator.Mult(a.denominator).Add(this.denominator.Mult(a.numerator));
MyLong y = this.denominator.Mult(a.denominator);
MyLong gcd = MyLong.gcd(x, y);
return new Fraction(x.Divide(gcd),y.Divide(gcd));
}
Fraction Sub(Fraction a)
{
MyLong x = this.numerator.Mult(a.denominator).Sub(this.denominator.Mult(a.numerator));
MyLong y = this.denominator.Mult(a.denominator);
MyLong gcd = MyLong.gcd(x, y);
return new Fraction(x.Divide(gcd),y.Divide(gcd));
}
public String
toString()
{
return numerator + "/" + denominator;
}
}
class FractionMultDiv extends Fraction
{
FractionMultDiv(String s)
{
super(s);
}
FractionMultDiv(MyLong numerator, MyLong denominator)
{
super(numerator, denominator);
}
FractionMultDiv
Mult(Fraction a)
{
MyLong x = this.numerator.Mult(a.numerator);
MyLong y = this.denominator.Mult(a.denominator);
MyLong gcd = MyLong.gcd(x, y);
return new
FractionMultDiv(x.Divide(gcd),y.Divide(gcd));
}
FractionMultDiv
Divide(Fraction a)
{
MyLong x = this.numerator.Mult(a.denominator);
MyLong y = this.denominator.Mult(a.numerator);
MyLong gcd = MyLong.gcd(x, y);
return new
FractionMultDiv(x.Divide(gcd),y.Divide(gcd));
}
}
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
while(con.hasNext())
{
FractionMultDiv a = new
FractionMultDiv(con.next());
char ch = con.next().charAt(0);
FractionMultDiv b = new
FractionMultDiv(con.next());
FractionMultDiv res;
if (ch == '*')
res = a.Mult(b);
else
res = a.Divide(b);
System.out.println(res);
}
con.close();
}
}