Description
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。
下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
HINT
数据范围
$1\leqslant m,n \leqslant 1000$
这道题一眼看去有一个非常显然的想法，那就是先用组合数算出任选三点出来的方案数，最后再减去三点共线的情况即可。那么关键就在于如何求三点共线的数目。
首先，我们要用到一个公式：设两个整点分别为$(x_1,y_1)$，$(x_2,y_2)$，那么两点之间连线上的整点数目为$gcd(|x_2-x_1|,|y_2-y_1|)$。
我觉得这个公式需要证明一下(其实很简单)。
首先，这条直线可以平移一下，使得$x_1=y_1=0$。为了考虑方便，我们这里还设$x_2 \geqslant 0,y_2 \geqslant 0$
设$\Delta x=x_2,\Delta y =y_2$(只是为了好看一点)，连线上整点的坐标为$(x,y)$，那么显然有：$$\frac{x}{\Delta x}=\frac{y}{\Delta y}$$
设$r=gcd(\Delta x,\Delta y)$，$\Delta x=ar$，$\Delta y=br$，那么有：$$xb=ya$$
由于$a,b$互质，$x,y$为整数，于是我们就得到了$$x=ka,y=kb(k \in Z)$$；
由于$0 \leqslant x \leqslant \Delta x,0\leqslant y \leqslant \Delta y$且$x,y$为整数
所以$x,y$的取值共有$\Delta x / a=\Delta y/b=gcd(\Delta x,\Delta y)$种
除去$x=\Delta x,y=\Delta y$这组解，这两点连线上共有$gcd(\Delta x,\Delta y)-1$个整点。
接下来我们可以直接枚举线段，然后计算有线段上有多少个整点；然而这样复杂度是$O(n^2m^2)$的。
然后，显然每一条线段经过平移，使它的左端点在矩形左下角或者左上角。由于向下和向上的线段对称，所以只需要计算一种即可。
所以就固定一个端点为$(0,0)$，枚举另外一个端点在哪里，计算一下即可。
下面贴代码(话说这么一道题我好像讲复杂了)：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std;
typedef long long llg; int n,m;
llg ans,x; int gcd(int a,int b){
if(!b) return a;
int r=a%b;
while(r) a=b,b=r,r=a%b;
return b;
} int main(){
File("a");
scanf("%d %d",&n,&m);
x=(n+1)*(m+1); ans=x*(x-1)*(x-2)/6;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(i|j){
llg x=(llg)(n-i+1)*(llg)(m-j+1);
ans-=x*(llg)(gcd(i,j)-1);
if(i && j) ans-=x*(llg)(gcd(i,j)-1);
}
printf("%lld",ans);
return 0;
}