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???
The statement of the problem says: "Output the value of the convergent continued fraction of order k of the square root of x as an IRREDUCIBLE fraction." But it is well-known, that every such convergent fraction is irreducible. However after taking modulo it may become reducible. So I thought I should reduce the answer in this case. But it is not true! You don't have to do it. Otherwise you'll get WA#8.
May admins clarify this misunderstanding somehow, please?
Sqrt(2)=1+1/(2+1/(2+1/(2+1/...... =[1,2,2,2,2,2,2,2,2......] the loop number is 1 so if k=10^9 , it can fail to calculate [1,2],[1,2,2],[1,2,2,2],[1,2,2,2,2]......
