先考虑 ((n,m)) 能走到的充要条件。注意到 (a,b) 和 (b,a) 两种各可以走无限步，每步加减号自选，唯一的限制就是第一 / 二种两个贡献系数要同奇同偶。设第一种两个贡献系数为 (x,z)，第二种为 (y,w)，那么可以枚举每种的奇偶性，充要条件就是下面这四个二元线性丢番图方程组至少有一个有解：
[egin{cases}2xa+2yb=n\2zb+2wa=mend{cases}\egin{cases}2xa+(2y+1)b=n\2zb+(2w+1)a=mend{cases}\egin{cases}(2x+1)a+2yb=n\(2z+1)b+2wa=mend{cases}\egin{cases}(2x+1)a+(2y+1)b=n\(2z+1)b+(2w+1)a=mend{cases}
]
即至少满足以下四个条件中的一个（其中 (d=gcd(a,b))）：
[2dmid n,m\2dmid n-b,m-a\2dmid n-a,m-b\2dmid n-a-b,m-a-b
]
然后考虑 (p(a,b)=1) 的充要条件。如果不看上面四个条件的话，若 (d>1)，那么最多只能走到那些 (dmid n,m) 的 ((n,m))，不可能走到全部，所以 (d=1) 是必要条件，于是用 (2) 代换上面的 (2d)。此时显然 (a,b) 的具体值不重要，重要的是 (amod 2,bmod 2)。分个类可以发现需要 (a otequiv bpmod 2)。于是充要条件推出来是 (aperp b,2 mid a+b)。
于是要求
[ans=sum_{i=1}^nsum_{j=1}^n[iperp j][2
mid i+j]
]
这个式子的值。莫反推推：
[egin{aligned}ans&=sum_{i=1}^nsum_{j=1}^n[2
mid i+j]sum_{omid i,omid j}mu(o)\&=sum_omu(o)[2
mid o]2!leftlceildfrac{leftlfloordfrac no
ight
floor}2
ight
ceil!leftlfloordfrac{leftlfloordfrac no
ight
floor}2
ight
floorend{aligned}
]
整除分块，于是要求关键点处的 (f=mu imes g) 的前缀和（其中 (g(x)=xmod 2)）。幸运的是，(g) 不仅是个积性函数，还是完全积性函数。于是 (f) 就是个经典数论函数乘以完全积性函数，就套路地 ((mu imes g)*g=epsilon) 一下就可以杜教筛了，(g) 和 (epsilon) 的前缀和都随便算。