Đường đi ít chi phí nhất trong bài mọi con đường về không

Submit solution
Points: 4 (partial)
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Số nguyên dương n nếu phân tích thành tích hai số tự nhiên a∗b(a<=b) thì nó sẽ sinh ra số tự nhiên m=(a−1)∗(b+1) cứ tiếp tục như vậy nếu m>0 nó tiếp tục sinh ra số tiếp theo. Bài toán đặt ra cho số n nguyên dương nó sẽ sinh ra các con và các con lại tiếp tục sinh ra các cháu ... cứ như vậy tới khi sinh ra tới các số 0 thì sẽ tạo thành một cây.

Biết rằng nếu chi phí để từ nút n=a∗b sinh ra nút m=(a−1)∗(b+1) được tính như sau

  • Nếu b chia hết cho a thì chi phí sẽ là b/a
  • Ngược lại sẽ chi phí là b+a

Ví dụ m=12 ta có cây được sinh ra như sau

enter image description here

Toto muốn biết là từ một số tự nhiên s đi đến f thì đường đi với chi phí ít nhất là bao nhiêu

Input:

Dòng đầu tiên là số bộ kiểm thử t(1≤t≤100)

Các dòng tiếp theo gồm t dòng mỗi dòng chứa một hai số tự nhiên s,f(0≤f≤s≤1000)

Output:

Gòm t dòng lần lượt tương ứng là kết quả đối với từng giá trị đầu vào trong trường hộp không đi được thì xuất ra −1

Ví dụ

Input

Copy
3
30 10
100 10
30 29

Output

Copy
33
66
-1

Giải thích

Test 1 : cách đi như sau 30->22->12->10

Test 2 : cách đi như sau 100->99->68->35->32->27->20->18->10

tichpx

Comments


  • 0
    nguyentrieu  commented on Feb. 11, 2023, 5:50 p.m. ← edit 2

    cho em xin code bài này với ạ