昨天考试的神仙题

对于一个状态(x,y,z)，有三种转移方案，往外跳两种，往里跳只有1种(考试的时候没有意识到)

那么可以看作一棵树，往外跳是子节点，往里跳是父亲

问题转换成树上两个点求最短路，这样就只用往里面跳了

考虑往里面跳是相当于一个辗转相除的，复杂度是logK，根据求LCA倍增的思想，不停往上跳就好。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;bool check(int ax,int ay,int az,int bx,int by,int bz){ int t1,t2,w; t1=ay-ax,t2=az-ay,w=0; if(t1>t2){swap(t1,t2);w^=1;} while((t2-1)/t1>0) { int c=(t2-1)/t1; if(w==0){ax+=c*t1;ay+=c*t1;} else {ay-=c*t1,az-=c*t1;} t2=t2-t1*c; swap(t1,t2);w^=1; } t1=by-bx,t2=bz-by,w=0; if(t1>t2){swap(t1,t2);w^=1;} while((t2-1)/t1>0) { int c=(t2-1)/t1; if(w==0){bx+=c*t1;by+=c*t1;} else {by-=c*t1;bz-=c*t1;} t2=t2-t1*c; swap(t1,t2);w^=1; } return ax==bx&&ay==by&&az==bz;}int getdep(int x,int y,int z){ int t1=y-x,t2=z-y,ret=0; if(t1>t2)swap(t1,t2); while((t2-1)/t1>0) { int c=(t2-1)/t1; ret+=c; t2=t2-t1*c; swap(t1,t2); } return ret;}void jumpK(int &x,int &y,int &z,int d){ int t1=y-x,t2=z-y,w=0; if(t1>t2){swap(t1,t2);w^=1;} while(d>0) { int c=min(d,(t2-1)/t1); d-=c; if(w==0){x+=c*t1;y+=c*t1;} else {y-=c*t1,z-=c*t1;} t2=t2-t1*c; swap(t1,t2);w^=1; }}int main(){ freopen("2.in","r",stdin); freopen("2.out","w",stdout); int ax,ay,az,bx,by,bz; scanf("%d%d%d%d%d%d",&ax,&ay,&az,&bx,&by,&bz); if(ax>ay)swap(ax,ay); if(bx>by)swap(bx,by); if(ax
           
            
             =0;i--) if(db>(1<