先考虑 \((n,m)\) 能走到的充要条件。注意到 \(a,b\) 和 \(b,a\) 两种各可以走无限步，每步加减号自选，唯一的限制就是第一 / 二种两个贡献系数要同奇同偶。设第一种两个贡献系数为 \(x,z\)，第二种为 \(y,w\)，那么可以枚举每种的奇偶性，充要条件就是下面这四个二元线性丢番图方程组至少有一个有解：

\[\begin{cases}2xa+2yb=n\\2zb+2wa=m\end{cases}\\\begin{cases}2xa+(2y+1)b=n\\2zb+(2w+1)a=m\end{cases}\\\begin{cases}(2x+1)a+2yb=n\\(2z+1)b+2wa=m\end{cases}\\\begin{cases}(2x+1)a+(2y+1)b=n\\(2z+1)b+(2w+1)a=m\end{cases} \]

即至少满足以下四个条件中的一个（其中 \(d=\gcd(a,b)\)）：

\[2d\mid n,m\\2d\mid n-b,m-a\\2d\mid n-a,m-b\\2d\mid n-a-b,m-a-b \]

然后考虑 \(p(a,b)=1\) 的充要条件。如果不看上面四个条件的话，若 \(d>1\)，那么最多只能走到那些 \(d\mid n,m\) 的 \((n,m)\)，不可能走到全部，所以 \(d=1\) 是必要条件，于是用 \(2\) 代换上面的 \(2d\)。此时显然 \(a,b\) 的具体值不重要，重要的是 \(a\bmod 2,b\bmod 2\)。分个类可以发现需要 \(a\not\equiv b\pmod 2\)。于是充要条件推出来是 \(a\perp b,2\nmid a+b\)。

于是要求

\[ans=\sum_{i=1}^n\sum_{j=1}^n[i\perp j][2\nmid i+j] \]

这个式子的值。莫反推推：

\[\begin{aligned}ans&=\sum_{i=1}^n\sum_{j=1}^n[2\nmid i+j]\sum_{o\mid i,o\mid j}\mu(o)\\&=\sum_o\mu(o)[2\nmid o]2\!\left\lceil\dfrac{\left\lfloor\dfrac no\right\rfloor}2\right\rceil\!\left\lfloor\dfrac{\left\lfloor\dfrac no\right\rfloor}2\right\rfloor\end{aligned} \]

整除分块，于是要求关键点处的 \(f=\mu\times g\) 的前缀和（其中 \(g(x)=x\bmod 2\)）。幸运的是，\(g\) 不仅是个积性函数，还是完全积性函数。于是 \(f\) 就是个经典数论函数乘以完全积性函数，就套路地 \((\mu\times g)*g=\epsilon\) 一下就可以杜教筛了，\(g\) 和 \(\epsilon\) 的前缀和都随便算。