题解 | 乘除

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) { 
        int A, B, k;
        cin >> A >> B >> k;
        int min_step = INT_MAX;
        queue<pair<int, int>> que;
        if(A == B){ //直接相等
            cout << 0 << endl;
            continue;
        }else if(k==1){ //k为1，无论怎么操作，A的值不会变，直接跳出
            cout << -1 << endl;
            continue;
        }else{
            que.push(pair<int, int> (A, 0)); //队列对每次进行t/k向上取整和t/k向下取整进行管理
            while(!que.empty()){ // 直到t/k==0，或者出现两次t/k==1，停止循环
                pair<int, int> t = que.front(); //first为t，second为除k的次数
                // cout << t.first << endl;
                que.pop();
 
                if(t.first < B && B%k!=0){ // 枝剪法，当t小于B时，B如果不是k的倍数则不可能通过t*k得到B
                    break;
                }
			  
			    int bs=0;
                bool b = true; // 标识符，判断是否存在整数bs，使得t * k^bs = B
                if(B%t.first==0){ // B是否是t的倍数
                    int tt = B/t.first; //也可通过logk(B/t)是否是整数实现
                    while(tt%k==0){
                        bs++; //k的bs次方
                        tt/=k;
                    }
                    if(tt!=1){
                        b = false; // t不能通过乘以k^bs得到B
                    }
                }
                
                if(B%t.first==0 && b){
                    int step = t.second+bs; //除法的次数+乘法的次数
                    min_step = min(step, min_step);//最小次数
                }else{
                    pair<int, int> t1(floor(1.0*t.first/k), t.second+1); // 向上取整
                    pair<int, int> t2(ceil(1.0*t.first/k), t.second+1); // 向下取整
                    if(t2.first && t2.first!=t.first){
                        // cout << t2.first << ',' << t.first<<endl;
                        que.push(t2);
                    }
                    if(t1.first && t1.first!=t.first){ // 避免1/n向上取整=1，产生循环
                        // cout << t1.first << ',' << t.first <<endl;
                        que.push(t1);
                    }


                }
            }
        }
        if(min_step==INT_MAX){
            cout << -1 << endl;
        }else{
            cout << min_step << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")