你可以对数字做两种操作把数字除以K取整⌊/⌋⌊x/K⌋。这会让数字变小相当于在族谱里往上找父亲。把数字变成y满足⌊/⌋⌊y/K⌋x。这相当于x 是y 的父亲也就是在族谱里往下找孩子。目标从X走到Y最少要走几步核心思路找共同祖先算法细节记录所有父亲寻找儿子举个栗子假设10K10123X12345Y45。Y 的族谱(记录在map里)4545(距离00)44(距离11,4545的父)00(距离22,44的父)X 去认亲第一轮:X是123123。Y的族谱里有123123吗没有。X找爸爸变成1212。第二轮:X是1212。Y的族谱里有1212吗没有。X找爸爸变成11。第三轮:X是11。Y的族谱里有11吗没有。X找爸爸变成00。第四轮:X是00。Y的族谱里有00吗有距离Y是22步。计算:X走了3步:123→/1012→/101→/100123/10​12/10​1/10​0Y走了2步0→×1044→×105450×104​4×105​45。总步数:325325步。代码实现#includebits/stdc.husing namespace std;#define int long longsigned main(){int T;cinT;while(T–){int x,y,k;cinxyk;mapint,intm;int cy,d0;while(c0)m[c]d,c/k;m[0]d,cx,d0;int ansINT_MAX;while(1){if(m.count©)ansmin(ans,dm[c]);if(!c)break;c/k,d;}coutans“\n”;}return 0;}