这道题还是不错的，不过一开始读错了题，以为要求线段个数，那样的话是一个裸的莫比乌斯反演，写完过不了大样例才发现是求直线。于是直接死了。
考后看题解。
发现$ans=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}[gcd(i,j)==1]((n-i)(m-j)-max(0,n-2i)*max(0,m-2j))$
什么意思呢？
首先枚举斜率，然后计算这个斜率的直线的个数，这样的话我们不能用相同的斜率来重复计算，所以要[gcd(i,j)==1]。
那么考虑一下哪些点可以作为一个线的代表元素？这个点的前驱必然在点阵中，后继必然不再点阵中。
这样的话是一个矩形的右上边框的贡献，也就是上面那个式子的后半部分。
考虑优化。
卡了空间只能开两个数组。于是我用一个存满足$gcd(i,j)==1$的i的和，另一个是j的。
这样的话，需要快速知道的就是
1.这个要乘n。反演一下。
$\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}[gcd(i,j)==1]$
$=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{m-1}\sum\limits_{d|gcd(i,j)}\mu(d)$
$=\sum\limits_{d=1}^{min(n-1,m-1)}\mu(d)\lfloor\frac{n-1}{d}\rfloor\lfloor\frac{m-1}{i}\rfloor$
2.然后是后面的ij项。
$\sum\limits_{i=1}^{n-1}\sum\limits{j=1}^{m-1}[gcd(i,j)==1]ij$
$\sum\limits_{i=1}^{n-1}\sum\limits{j=1}^{m-1}ij\sum\limits_{d|gcd(i,j)}\mu(d)$
$\sum\limits_{d=1}^{min(n-1,m-1)}mu(d)d^2\lfloor\frac{n(n+1)}{2}\rfloor\lfloor\frac{m(m+1)}{2}\rfloor$
然后就可以根号询问了。
得解。
原文：https://www.cnblogs.com/Lrefrain/p/11524431.html