题目连接 题意，给你一个坐标（x，y），在周围的8给方向里，如果gcd（x，y）！=1，则可以走过去，这是等概率的。为最后回到起点的概率。 题解： 结论：如果不可以经过对角线，ans=（起点的度数+1）/（图的总度数+联通块大小）。如果经过对角线即为0/1。因为联通快不会很大。所以可以直接搜索 。 下面是ac代码：
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); using namespace std; const int N = 2e3+5; const int dir[2][8] = {{1, 1, 1, 0, 0, -1, -1, -1}, {-1, 0, 1, 1, -1, -1, 0, 1}}; map<pair<ll, ll>, int> su; bool flag = 0; int sum = 0; void dfs(ll x, ll y) { if (x == y) { flag = 1; return; } if (su.find(pr(x, y)) != su.end()) return; // cout << x << " " << y << endl; su[pr(x, y)] = 0; int cnt = 0; for (int i = 0; i < 8; i++) { ll dx = x + dir[0][i], dy = y + dir[1][i]; if (__gcd(dx, dy) == 1) continue; cnt++; dfs(dx, dy); } su[pr(x, y)] = cnt, sum += cnt; return; } int main() { int t; cin >> t; while(t--) { sum = 0; flag = 0; su.clear(); ll x, y; scanf("%lld%lld", &x, &y); int dx = 0; for (int i = 0; i < 8; i++) dfs(x, y); if (flag) { puts("0/1"); continue; } else { int dx = su[pr(x, y)] + 1; int z = su.size() + sum; printf("%d/%d\n", dx/__gcd(dx, z), z / __gcd(dx, z)); } } return 0; }