[CQOI2014]数三角形

正难则反
合法答案 = 所有三角形 - 水平（竖直）共线 - 斜共线

所有三角形$C_{\left (n+1 \right )\left (m+1 \right )}^{3}$
水平（竖直）共线$C_{n+1}^{3}\left ( m+1 \right )+C_{m+1}^{3}(n+1)$

斜共线不好直接求，考虑枚举向量$\left ( i,j \right )\ i\leq n+1,j\leq m+1$
为了保证不重不漏，第一和第二个点分别为$\left ( i,j \right )$起点与终点，第三个点在$\left ( i,j \right )$中间
对于一组$\left ( i,j \right )$，共有$\left ( n-i+1 \right )\left ( m-j+1 \right )$种可能，其中第三个点还有$gcd\left ( i,j \right )-1$种可能
考虑到左右对称，答案还需要$*2$

#include<cstdio>
#define LL long long
int n,m;
LL ans=0;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL C(LL m,LL n)
{
    if (m<n) return 0;
    LL ret=1;
    for(LL i=1;i<=n;i++)
        ret=ret*(m-i+1)/i;
    return ret;
}
int main()
{
    n=read()+1,m=read()+1;
    ans=C(n*m,3);
    ans-=C(m,3)*n+C(n,3)*m;
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            ans-=(n-i)*(m-j)*(gcd(i,j)-1)*2;
    printf("%lld\n",ans);
    return 0;
}