题意：给出一个a*b的网格，在网格上取不共线的三点构成三角形，求三角形总数。
分析：就是一一道简单的组合数计算题目，设总结点数为n，则取三个节点的个数为C（n，3），然后减去横向、竖向、斜向的三点共线的个数即可，斜线三点共线等价于所枚举的矩形的长宽成倍数关系，即gcd不为1
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 long long gcd(long long a, long long b){ 5 if(a%b==0) return b; 6 return gcd(b, a%b); 7 } 8 int main(){ 9 long long a, b; 10 int cas = 1; 11 while(scanf("%lld%lld", &a, &b)!=EOF && (a||b)){ 12 long long n = (a+1)*(b+1); 13 long long sum1 = n*(n-1)*(n-2)/6; //C(n,3) 14 long long sum2 = (b+1)*(a+1)*a*(a-1)/6 + (a+1)*(b+1)*b*(b-1)/6; //横向或竖向三点共线的个数 15 long long sum3 = 0; //斜线上三点共线的个数的一半 16 int i, j; 17 for(i=2; i<=a; i++) 18 for(j=2; j<=b; j++) 19 sum3 += (gcd(i,j)-1) * (a-i+1) * (b-j+1); 20 a++;b++; 21 long long ans = sum1 - 2*sum3 - sum2; 22 printf("Case %d: %lld\n", cas++, ans); 23 } 24 return 0; 25 }
