Problem hidden
HSPC14A - Biến đổi cặp số
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/hspc14a
Từ cặp số (a, b) gồm 2 số nguyên dương, có thể sử dụng 1 trong 3 phép biến đổi sau để tạo ra
cặp số mới
•
•
•
(a,b) → (a, a+b)
(a,b) → (a+b, b)
(a,b) → (b,a)
Bắt đầu từ cặp số (1, 1) hãy dùng ít phép biến đổi nhất để tạo ra một cặp số có chứa số N.
Từ cặp số (a, b) gồm 2 số nguyên dương, có thể sử dụng 1 trong 3 phép biến đổi sau để tạo ra
cặp số mới
(a,b) → (a, a+b)
(a,b) → (a+b, b)
(a,b) → (b,a)
Bắt đầu từ cặp số (1, 1) hãy dùng ít phép biến đổi nhất để tạo ra một cặp số có chứa số N.
Input
Dòng đầu chứa số test T. Tiếp theo là T test, mỗi test chứa một số 1 ≤ N ≤ 10^6.
Output
Ứng với mỗi test, in ra trên một dòng số bước biến đổi ít nhất.
Example
Input: 4
1
3
5
7 Output: 0
2
3
4
Added by: | Lê Đôn Khuê |
Date: | 2014-07-27 |
Time limit: | 4s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | HSPC 2014 |