I thought the algo is to find the loop of continued fraction.
But it seems that if the loop is too small, 10^9 would make this algo fail.

Give some hint plz.

for example:

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]......

Accepted now.
No very complicated number theory is needed.
All you need is the chapter about continued fraction in any copy of basic number theory.