数学课想出来的奇怪做法。

以下为方便讨论，令 $m=\dfrac{n}{2}$。

由已知得，对于一个 $m$，其地砖边上的点必然满足以下条件：

• $m|x$ 且 $m|y$；

• $x+y\equiv m\pmod {2m}$；

等价于：

• $m|\gcd(x,y)$；

• $x+y\not\equiv 0\pmod {2m}$；

所以令 $S=\{m|[m|\gcd(x,y)]\}$，$R=\{m|x+y\not\equiv 0\pmod {2m}\}$，$T=S\cap R$，答案即为 $|T|$。

$|T|$ 不好计算，正难则反，令 $U=\complement_ST=\begin{cases}\{m|[m|\gcd(x,y,\frac{x+y}{2})]\}&x+y\equiv 0\pmod 2\\\emptyset&\mathrm{otherwise}\end{cases}$，计算 $|U|$ 即可。答案为 $|S-U|$。

$[1,10^7]$ 以内所有数的因数个数可以对于每个数暴力枚举倍数预处理，令 $A=10^7$，时间复杂度 $O(A\log A)$。但因为常数小并且时限 $3\mathrm{s}$ 所以可以过。

放代码：

#include<bits/stdc++.h>
using namespace std;
int a[10000001];
int main(){
  ios::sync_with_stdio(false);
  for(int i=1;i<=1e7;i++)
    for(int j=1;i*j<=1e7;j++)a[i*j]++; // 预处理
  int t; cin>>t;
  while(t--){
    int x,y,c=0; cin>>x>>y;
    int g=gcd(x,y),m=gcd(x+y>>1,g);
    cout<<a[g]-(x+y&1?0:a[m])<<'\n'; // 计算答案
  }
  return 0;
}