https://vjudge.net/problem/UVALive-3295
题意：
数出n行m列的网格顶点能组成多少个三角形。
思路：
直接去数的话比较麻烦，这道题目是可以重复的，只要位置不同就可以了。
所有的情况就是,接下来剪去共线的情况。
①在同一行的共线，(n+1)×C(m+1,3)
②在同一列的共线，(m+1)×C(n+1,3)
③在斜线上的共线，gcd(i,j)-1表示起点(0,0)到终点(i,j)的共线情况，也就是说，此时已经确定了两个点。f(i,j)=f(i-1,j)+f(i,j-1)。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std; typedef long long LL;
const int maxn=+; LL f[maxn][maxn]; LL gcd(LL a,LL b)
{
return b==?a:gcd(b,a%b);
} LL c(LL n, int m)
{
return n*(n-)*(n-)/;
} void init()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
f[i][j]=gcd(i,j)-; for(int i=;i<=;i++)
for(int j=;j<=;j++)
f[i][j]+=f[i-][j]; for(int i=;i<=;i++)
for(int j=;j<=;j++)
f[i][j]+=f[i][j-]; for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
printf("f[%d][%d]: %d\n",i,j,f[i][j]);
}
} int main()
{
//freopen("D:\\input.txt","r",stdin);
int n,m;
int kase=;
init();
while(~scanf("%d%d",&n,&m) && n && m)
{
n++, m++;
LL ans=c(n*m,)-n*c(m,)-m*c(n,);
for(int i = ; i < n; i ++)
for(int j = ; j < m; j ++)
ans -= *f[i][j];
printf("Case %d: %lld\n",++kase,ans);
}
return ;
}