给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input 输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
Sample Input 2 2 Sample Output 76
数据范围 1<=m,n<=1000
找规律，之后组合数，然后排除不合法的。
#include <iostream> #include <cstdio> #define LL long long #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; int n,m; LL c[1005005][4]; LL ans,tmp; inline int gcd(int a, int b) { return !b ? a : gcd(b, a%b); } void getc() { c[0][0] = 1; for(int i = 1; i <= n*m; i++) { c[i][0] = 1; for(int j = 1; j <= 3; j++) c[i][j] = c[i-1][j-1]+c[i-1][j]; } } void solve() { ans = c[n*m][3]-n*c[m][3]-m*c[n][3]; for(int i = 1; i < n; i++) for(int j = 1; j < m; j++) { tmp = gcd(i, j)+1; if(tmp > 2) ans -= (tmp-2)*2*(n-i)*(m-j); } } int main() { scanf("%d%d",&n,&m); n++; m++; getc(); solve(); printf(AUTO,ans); return 0; }