Discussion @ 1814. Continued Fraction @ Timus Online Judge

Unusual problem on 2x2 matrix multiplication, but... (+)

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 3 Mar 2011 18:24

You do some matrix maltiplication and get an answer in the form (a%10^9)/(b%10^9), but it is not guaranteed that gcd (a, b) == 1. How to get irreducible fraction now???

Re: Unusual problem on 2x2 matrix multiplication, but... (+)

Posted by Shen Yang 29 Apr 2018 17:17

it can be proved be deduction that if a/b is irreducible fraction then a[i]+a/b is also irreducible fraction

problem descrption means original a/b is irreducible not after mod...

Discussion of Problem 1814. Continued Fraction