Description

给定一个 \(n \times m\) 的网格, 请计算三点都在格点上的三角形共有多少个. 注意三角形的 三点不能共线.

Input

输入一行, 包含两个空格分隔的正整数 \(m\) 和 \(n\).

Output

输出一个正整数, 为所求三角形数量.

Sample Input

2 2

Sample Output

76

Data Range

对于所有的数据, 满足:\(1 \leq m, n \leq 1000\)

Explanation

首先可以任意选择三个互异的点构成一个 “伪三角形”, 即该三角形有可能退化成为一条线. 然后从这些三角形中挑出退化的减去即可.

退化的有三种情况, 分别为:

  1. 三点在同一行上的, 这个可以直接用组合数去掉;
  2. 三点在同一列上的, 做法同上;
  3. 三点在斜线上的, 这个需要处理出 “斜率” 的最大公约数然后再用组合数搞出来.

具体的公式这里就不写了, 反正代码也比较好看 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1010, maxm = 1001000;

lli gcd(lli a, lli b) {
    return __gcd(a, b);
}
lli C[maxm][4];

lli n, m;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &m);
    // Because this indicated grids instead of nodes
    n += 1, m += 1;
    // Calculating combinations, using Yang Hui triangle
    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];
    }
    // Depleting and rejecting
    lli res = C[n*m][3];
    // Removing those on the same row and same column
    res -= n*C[m][3] + m*C[n][3];
    // Removing those on a diagonal
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) {
            lli tmp = gcd(i, j) + 1;
            if (tmp < 3)
                continue;
            res -= (tmp-2) * 2 * (n-i) * (m-j);
        }
    // Output...
    printf("%lld\n", res);
    return 0;
}