传送门

题意

好点集合的定义如下，对于一个点（x,y），如果gcd(x,y)>1，则为好点。
给你一个点，从该点开始，等可能的前往周围的八个方向的好点，或停留在原地。
问你走过无穷步之后，回到初始点的概率是多少

思路

“图上随机游走”算法结论就是在建出无向图后，答案就是 “起点的度数 + 1 ” 除以 “总度数 + n”

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 20005
#define mod 998244353
ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);
}
struct node{
    ll u,v;
    bool operator<(const node &x)const{
        if(u!=x.u) return u<x.u;
        return v<x.v;
    }
}tmp,tmp1;
ll pos[9][2]={{0,1},{0,-1},{-1,0},{-1,-1},{-1,1},{1,-1},{1,0},{1,1}};
int main(){
    ll i, j, k, t, n, x, y;
    scanf("%lld",&t);
    while(t--){
        set<node> s;    
        ll sum=0,chu=0;
        scanf("%lld%lld",&tmp.u,&tmp.v);
        if(tmp.u==tmp.v){
        	printf("0/1\n");
        	continue;
		} 
        int flag=0;
        queue<node> q;
        q.push(tmp);
        s.insert(tmp);
        while(!q.empty()){
            tmp=q.front();
            q.pop();
            sum++; 
            for(i=0;i<8;i++){
                tmp1.u=tmp.u+pos[i][0];
                tmp1.v=tmp.v+pos[i][1];
                if(tmp1.u==tmp1.v){
                    flag=1;break;
                } 
                if(gcd(tmp1.u,tmp1.v)==1) continue;
                sum++;
                if(s.count(tmp1)) continue;
                s.insert(tmp1);
                q.push(tmp1);
            }
            if(flag) break;
            if(!chu) chu=sum;
        }
        if(flag){
        	printf("0/1\n");
        	continue;
		} 
        ll g=gcd(chu,sum);
        printf("%lld/%lld\n",chu/g,sum/g);
    }
}