RT。$n=56,111,171,176$ 时答案各多了 $2$（然而 AC 了），请求 hack。

@小粉兔

AC Code：

#include<bits/stdc++.h>
using namespace std;
bool res(int x,int y)
{
    while(y)
    {
        int a=y,b=x%y;
        x=a,y=b;
    }
    return (x>1)?1:0;
}
bool c[252][252];
void init(int n)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            c[i][j]=res(i,j);
}
int q1[65012],q2[65012];
int f=1,t=0;
int ff(int x,int y)
{
    if(!c[x][y]) return 0;
    f=1,t=0;
    t++,q1[t]=x,q2[t]=y;
    int cc[2]={1,0},now=1;
    while(f<=t)
    {
        int cnt=t-f+1;
        for(int i=1;i<=cnt;i++)
        {
            c[q1[f]][q2[f]]=0;
            if(c[q1[f]][q2[f]-1]) t++,q1[t]=q1[f],q2[t]=q2[f]-1,cc[now]++;
            if(c[q1[f]][q2[f]+1]) t++,q1[t]=q1[f],q2[t]=q2[f]+1,cc[now]++;
            if(c[q1[f]-1][q2[f]]) t++,q1[t]=q1[f]-1,q2[t]=q2[f],cc[now]++;
            if(c[q1[f]+1][q2[f]]) t++,q1[t]=q1[f]+1,q2[t]=q2[f],cc[now]++;
            f++;
        }
        now^=1;
    }
    return max(cc[0],cc[1]);
}
int main()
{
    int n;
    cin>>n;
    init(n);
    int ans=0;
    bool ok=true;
    while(ok)
    {
        ok=false;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(c[i][j]==1&&c[i][j-1]==0&&c[i][j+1]==0&&c[i-1][j]==0&&c[i+1][j]==0) c[i][j]=0,ok=true,ans++;
                if(c[i][j]==1&&c[i][j-1]==1&&c[i][j+1]==0&&c[i-1][j]==0&&c[i+1][j]==0) c[i][j]=c[i][j-1]=0,ok=true,ans++;
                if(c[i][j]==1&&c[i][j-1]==0&&c[i][j+1]==1&&c[i-1][j]==0&&c[i+1][j]==0) c[i][j]=c[i][j+1]=0,ok=true,ans++;
                if(c[i][j]==1&&c[i][j-1]==0&&c[i][j+1]==0&&c[i-1][j]==1&&c[i+1][j]==0) c[i][j]=c[i-1][j]=0,ok=true,ans++;
                if(c[i][j]==1&&c[i][j-1]==0&&c[i][j+1]==0&&c[i-1][j]==0&&c[i+1][j]==1) c[i][j]=c[i+1][j]=0,ok=true,ans++;
            }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ans+=ff(i,j);
    cout<<ans;
    return 0;
}