Pro.ID22690 TitleEuclid again Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22690 AC0 Submit0 Ratio- 时间&空间限制描述Euclid Algorithm is effective when calculating GCD (Greatest Common Divisor) of two integers. Here is an example in C: long gcd ( long x, long y ) // assume that x ≥ y and x > 0 { if(!y) return x; return gcd(y, x%y); } Given two integers x and y, how many times the gcd function will be called finally? The following function will solve this problem: long f(long x, long y) // assume that x ≥ y and x > 0 { if(!y) return 1; else return f(y, x%y)+l; } Now let us define a new function g(k): g(k) = min{ x | f(x, y)=k, x ≥ y, x > 0, y ≥ 0 } Your task is to calculate the function g(k) efficiently. 输入The first line of the input data is an integer C, the number of the test cases followed. The input for each test case is an integer k ( 0 < k < 81 ). 输出Description Euclid Algorithm is effective when calculating GCD (Greatest Common Divisor) of two integers. Here is an example in C: long gcd ( long x, long y ) // assume that x ≥ y and x > 0 { if(!y) return x; return gcd(y, x%y); } Given two integers x and y, how many times the gcd function will be called finally? The following function will solve this problem: long f(long x, long y) // assume that x ≥ y and x > 0 { if(!y) return 1; else return f(y, x%y)+l; } Now let us define a new function g(k): g(k) = min{ x | f(x, y)=k, x ≥ y, x > 0, y ≥ 0 } Your task is to calculate the function g(k) efficiently. Input The first line of the input data is an integer C, the number of the test cases followed. The input for each test case is an integer k ( 0 < k < 81 ). Output The output should consist of C lines, one line for each test case, only containing one integer which represents the value of g(k). No redundant spaces are needed. Sample Input 1 Sample Output 1 Source 样例输入1 样例输出1 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 16:45 , Processed in 0.035045 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
