给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。
输入一行，包含两个空格分隔的正整数m和n。
输出一个正整数，为所求三角形数量。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 1e5 + 100; const int MAXM = 3e3 + 10; const double eps = 1e-5; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while (!isdigit(ch)) { if(ch == ‘-‘) ff = -1; ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if (x == 0) { putchar(‘0‘); return ; } if (x < 0) putchar(‘-‘), x = -x; static T tot = 0, ch[30]; while (x) { ch[++tot] = x % 10 + ‘0‘; x /= 10; } while (tot) putchar(ch[tot--]); } ll n, m, ans; inline ll C(ll x) { return x * (x - 1) * (x - 2) / 6; } inline int gcd(int x, int y) { if (x == 0) return y; return gcd(y % x, x); } int main() { read(n); read(m); ans = C((n + 1) * (m + 1)); ans -= (n + 1) * C(m + 1); ans -= (m + 1) * C(n + 1); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { ans -= 2ll * (gcd(i, j) - 1) * (m - j + 1) * (n - i + 1); } } write(ans); return 0; }
原文：https://www.cnblogs.com/AK-ls/p/11727343.html
