| ENG RUS | Timus Online Judge |
Обсуждение задачи 1814. Цепная дробьgerind How to solve it without BigDecimal? [1] // Задача 1814. Цепная дробь 22 мар 2024 14:52 gerind Re: How to solve it without BigDecimal? // Задача 1814. Цепная дробь 22 мар 2024 17:26 AC with big integers Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Unusual problem on 2x2 matrix multiplication, but... (+) [1] // Задача 1814. Цепная дробь 3 мар 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??? Shen Yang Re: Unusual problem on 2x2 matrix multiplication, but... (+) // Задача 1814. Цепная дробь 29 апр 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... bsu.mmf.team About condition... // Задача 1814. Цепная дробь 11 фев 2011 16:15 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? caoyuan9642 Is complicated and sophisticated number theory algorithms are involved? [2] // Задача 1814. Цепная дробь 31 янв 2011 21:23 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. caoyuan9642 Re: Is complicated and sophisticated number theory algorithms are involved? // Задача 1814. Цепная дробь 31 янв 2011 21:26 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]...... caoyuan9642 Re: Is complicated and sophisticated number theory algorithms are involved? // Задача 1814. Цепная дробь 1 фев 2011 12:46 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.
|