Đặt \(G = gcd(A,B)\), chia \(A\) cho \(G\), chia \(B\) cho \(G\). Đáp án của bài toán vẫn không thay đổi.

Dễ thấy, trong \(A\) và \(B\) lúc này không có TSNT chung. (Nếu có TSNT \(p\) chung, thì \(G\) không phải là ƯCLN)

Vì thế, để biến đổi từ \(A\) thành \(B\), ta có thể coi như là biến đổi từ \(A\) về \(1\), rồi biến đổi từ \(B\) về \(1\) (phép nhân và phép chia trong bài này tương tự nhau).

Ta cần tìm số bước chuyển ít nhất để biến số \(x\) bất kì về \(1\). Để làm điều này, ta có thể áp dụng thuật toán BFS.

Trong thực tế, một số \(x\) bất kì có rất ít ước. Vì thế, ta liệt kê toàn bộ ước của \(x\), và coi mỗi ước số như một đỉnh của đồ thị.

Có cạnh nối từ ước \(a\) tới ước \(b\) nếu \(a\) là bội của \(b\) và \(\frac{a}{b} \leq d\).

Số bước chuyển ít nhất để biến \(x\) thành \(1\) chính là đường đi ngắn nhất từ đỉnh đại diện cho \(x\) tới đỉnh đại diện cho \(1\) trên đồ thị.