시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 39 2 2 11.111%

문제

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.

입력

Dòng đầu chứa số test T. Tiếp theo là T test, mỗi test chứa một số 1 ≤ N ≤ 106.

출력

Ứng với mỗi test, in ra trên một dòng số bước biến đổi ít nhất.

예제 입력 1

4
1
3
5
7

예제 출력 1

0
2
3
4

힌트

  • (1 1)
  • (1 1) → (2 1) → (3 1) 
  • (1 1) → (2 1) → (2 3) → (2 5) 
  • (1 1) → (2 1) → (2 3) → (2 5) → (2 7)

출처

High School > Vietnam High School Programming Contest > HSPC 2014 A번

  • 데이터를 추가한 사람: kcm1700