Dãy phân số

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Sau một thời gian nghiên cứu, Nam đã đưa ra một phương pháp mã hoá các số nguyên thông qua dãy các phân số. Với số nguyên dương k, một dãy hữu hạn các phân số ai được định nghĩa như sau:

  • a1 = 1k

  • ai = xiyi = xi1+1yi11 khi i>1 với xiyi là một phân số tối giản;

  • Khi ai đạt đến một giá trị nguyên n, dãy phân số kết thúc (yi = 1).

Nam mã hoá hàm số f(k)=n.

Ví dụ: với k=20 có dãy biến như đổi sau:

120 -> 219 -> 318 = 16 -> 25 -> 34 -> 43 -> 52 -> 61 = 6

Kết quả f(20)=6.

Yêu cầu: Cho số nguyên dương x, bạn hãy giúp Nam tính f(x3 ).

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên dương T (T100) là số lượng giá trị x cần tính f(x3 );
  • Mỗi dòng trong số T dòng tiếp theo chứa một số nguyên dương x.

Kết quả: Ghi ra T dòng, mỗi dòng là giá trị f(x3) tương ứng với số nguyên dương x trong dữ liệu vào.

Ràng buộc:

  • Số test ứng với 50% số điểm của bài có: x100;
  • Số test khác ứng với 30% số điểm của bài có: x 104;
  • Số test còn lại ứng với 20% số điểm của bài có: x106.
Ví dụ:
INPUT
Copy
2
3
4
OUTPUT
Copy
6
12

Comments

Please read the guidelines before commenting.