思路分析
题目的大致意思为，每回给定两个整数 $a_i,b_i$，有两个基环树（一棵是树上的数是能变成 $1$ 的数，另一棵则是剩余的数），如果在同一棵树上，求两点的树上距离 $+1$。
变化的方式为将数的每位数平方加和，例如：
下面优四种做法思路：
根据 $a_i,b_i$ 的数据范围（$< 1e9$），发现经过一次操作，数最大可能是 $9^2\times 8=648$，所以我们可以将 $648$ 以内所有的数两两尝试，记录答案到一个数组中，对于每个询问直接输出（如果是大数，先进行一次操作，“缩数”），下面的预处理版代码。
或者可以直接现找先现用，因为每次询问暴力找甚至可以看成一个大常数（大约 $20$ 多点），由于数据过水这个跑的比预处理的要快，即下面的直接找版代码。
如果现找现用，每次进行记忆化。会更快一些（当然，只记录 $< 650$ 的数）。
还可直接连边（在范围内的数），跑基环树。答案即为两点树上的最短距离 $+1$。
在找的时候每回将序列的数标记，标记为时第几步走到当前位置的，这样在找到位置可以同时到达的时候，可以直接计算总步数。
一些细节
在暴力找时，入过其中一个的序列出现了两一个序列的数，先不要着急跳出循环，继续跑，因为可能会有更优的（是基环树们应该会有两次相遇，先相遇的不一定是最优的，下面的数据可以卡掉一些假法）。
（原数据没卡掉。）
读入：
61 25
30 145
0 0输出：
61 25
61 25 8
30 145
30 145 10
0 0直接找版代码
#include<cstdio>
#include<set>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=810;
int a_a[o_o],b_b[o_o];
int n_t(int k){//下一个数
int a_s=0;
while(k){
int k_i=k%10;
a_s+=k_i*k_i;
k=k/10;
}
return a_s;
}
int main(){
while(1){
int a_s=0x3f3f3f3f;//初始化最大值
int a_i=r_r(),b_i=r_r();
if(a_i==0&&b_i==0)break;//结束
printf("%d %d ",a_i,b_i);//将两个数先输出
if(a_i==b_i){//相等时两个长度都为 1
printf("2\n");
continue;
}
//初始化
memset(a_a,0,sizeof a_a);
memset(b_b,0,sizeof b_b);
int k_i=0;//记录当前时第几布
while(1){
k_i++;
if(b_i>o_o-10){//不记录
b_i=n_t(b_i);
continue;
}
if(b_b[b_i])break;//已经出现过，已经跑完基环
b_b[b_i]=k_i;//记录当数步数是第几步
b_i=n_t(b_i);//下一个值
}
k_i=0;//清空
while(1){
k_i++;
if(a_i>o_o-10){//不记录
a_i=n_t(a_i);
continue;
}
if(a_a[a_i])break;//已经出现过，已经跑完基环
if(b_b[a_i])a_s=min(a_s,k_i+b_b[a_i]);//两者都可以以这个数结尾，统计最小值
a_a[a_i]=k_i;//记录
a_i=n_t(a_i);//下一个值
}
if(a_s==0x3f3f3f3f)puts("0");//不在一个树上
else printf("%d\n",a_s);
}
return 0;
}预处理版代码
#include<cstdio>
#include<set>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=810;
int n;
int m_m[o_o][o_o];//记忆化
int n_t(int k){//下一个数
int a_s=0;
while(k){
int k_i=k%10;
a_s+=k_i*k_i;
k/=10;
}
return a_s;
}
int b_1[o_o],b_2[o_o];
int f_i(int a,int b){
if(a==b)return 2;//相同
//初始化
int a_s=0x3f3f3f3f;
memset(b_1,0,sizeof b_1);//a 形成的序列
memset(b_2,0,sizeof b_2);//b 形成的序列
int k_i=1;
bool b_p=0;//标记判断在同一棵树上
while(!b_2[b]||!b_1[a]){//只要有一个数没跑完基环就继续跑
if(a==b){
a_s=min(a_s,k_i*2);//最小化答案
b_p=1;//标记，不会被判成不在同一棵树上
}
if(!b_p&&b_2[a]&&b_1[b])return 0;//两个数都跑完了，但是没有在同一个树上
if(b_2[b]){//第二个数跑成环了
b_p=1;//标记
//记录最小值
if(b_1[a])a_s=min(a_s,k_i+min(b_2[b],b_1[a]));
else a_s=min(a_s,k_i+b_2[b]);
}
if(b_1[a]){//第一个数跑成环了
b_p=1;//标记
//记录最小值
if(b_2[b])a_s=min(a_s,k_i+min(b_2[b],b_1[a]));
else a_s=min(a_s,k_i+b_1[a]);
}
//没有标记过就继续变化
if(!b_1[b])b_1[b]=k_i,b=n_t(b);
if(!b_2[a])b_2[a]=k_i,a=n_t(a);
k_i++;//累计步数
}
//记录最小值
if(b_2[b]){
if(b_1[a])a_s=min(k_i+min(b_2[b],b_1[a]),a_s);
else a_s=min(a_s,k_i+b_2[b]);
}else a_s=min(a_s,k_i+b_1[a]);
return a_s;
}
void yv(){//预处理
for(int i=1;i<=o_o-10;i++)
for(int j=i;j<=o_o-10;j++)
m_m[j][i]=m_m[i][j]=f_i(i,j);//记忆化
}
int main(){
yv();
while(1){
int a=r_r(),b=r_r();
if(!a&&!b)break;//结束
printf("%d %d ",a,b);
if(a==b){//相同两者长度为 1
puts("2");
continue;
}
int a_s=0;//清空
//缩数
if(a>o_o)a=n_t(a),a_s++;
if(b>o_o)b=n_t(b),a_s++;
//输出
if(m_m[a][b])printf("%d\n",a_s+m_m[a][b]);
else puts("0");//不存在
}
return 0;
}
