A n * m grid as follow:
Count the number of triangles, three of whose vertice must be grid-points.
Note that the three vertice of the triangle must not be in a line(the right picture is not a triangle).
Input
The input consists of several cases. Each case consists of two positive integers n and m (1 ≤ n, m ≤ 1000).
Output
For each case, output the total number of triangle.
Sample Input
1 1 2 2
Sample Output
4 76
hint
hint for 2nd case: C(9, 3) - 8 = 76
此题就是求格点中三角形的个数。
就是找出三点不共线的个数。
n*m的矩形中有(n+1)*(m+1)个格点。
选出三个点的总个数为：C((n+1)*(m+1),3).
减掉共线的情况就是答案了。
首先是水平和垂直共线的情况：C(n+1,3)*(m+1)+C(m+1,3)*(n+1);
然后斜的共线的情况就是枚举矩形。
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; int gcd(int a,int b) { if(b==0)return a; return gcd(b,a%b); } long long Com(int n,int r) { if(n<r)return 0;//这个一定要 if(n-r<r)r=n-r; int i,j; long long ret=1; for(i=0,j=1;i<r;i++) { ret*=(n-i); for(;j<=r&&ret%j==0;j++)ret/=j; } return ret; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { long long ans=Com((n+1)*(m+1),3);//选三个点的所有组合数 for(int i=2;i<=n;i++) for(int j=2;j<=m;j++) { ans-=(long long)(gcd(i,j)-1)*(n-i+1)*(m-j+1)*2; } ans-=Com(n+1,3)*(m+1); ans-=Com(m+1,3)*(n+1); printf("%lld\n",ans);//ZOJ用lld,不能用I64d } return 0; }