#P47. 近似分数

    ID: 14 Type: Default 1500ms 16MiB Tried: 0 Accepted: 0 Difficulty: 10 Uploaded By: Tags>其他数学线性代数土拨鼠分数

近似分数

题目背景

连分数是一种特别的分数,通过辗转相除法得到分母(商),分子都是1,取前k项连分数的值,就得到相似度为k的分数,我们叫它“土拨鼠分数”,比如355/113≈22/7 算法为 a/(b+c/d)=ad/bc+d

题目要求

输入分子和分母,输出近似分数

输入

第一行两个整数m,n,分别是分子和分母 第二行为近似度k,1<=m<=n<=100001<=k1<=m<=n<=10000,1<=k

输出

两个数

样例

314159265 100000000
4
355 113