ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1467. Sum of Degrees

I don't understand, how to solve this using int64!
Posted by EfremovAleksei 28 Oct 2006 22:51
I spent about 10 hours and got AC.
I write long racional arithmetic.
Please, send me prog with int64 only (efrcom [at] yandex [dot] ru)

Edited by author 28.10.2006 22:51
Re: I don't understand, how to solve this using int64!
Posted by Denis Koshman 12 Aug 2008 05:28
Just reduce as much as possoble before actual operation:

tf operator + (const tf& f1, const tf& f2)
{
    int64 d  = gcd(f1.b, f2.b);
    int64 m1 = f2.b/d;
    int64 m2 = f1.b/d;
    return tf(f1.a*m1 + f2.a*m2, f1.b*m1);
}

tf operator - (const tf& f1, const tf& f2)
{
    int64 d  = gcd(f1.b, f2.b);
    int64 m1 = f2.b/d;
    int64 m2 = f1.b/d;
    return tf(f1.a*m1 - f2.a*m2, f1.b*m1);
}

tf operator * (const tf& f1, const tf& f2)
{
    int64 d1 = gcd(f1.a, f2.b);
    int64 d2 = gcd(f2.a, f1.b);
    return tf((f1.a/d1)*(f2.a/d2), (f1.b/d2)*(f2.b/d1));
}

tf operator / (const tf& f1, const tf& f2)
{
    assert(f2.a);
    return f1*tf(f2.b, f2.a);
}

fractions are further reduced inside 'tf(int64, int64)' constructor.

Edited by author 12.08.2008 05:28