数三角形

LibreOJ-10233-数三角形

实现

#include <iostream>
using namespace std;

typedef long long LL;
int n, m;

int gcd (int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
LL C (int n) {
    return (LL)n * (n - 1) * (n - 2) / 6;
}

int main () {
    cin >> n >> m;

    ++ n, ++ m;
    LL res = C(n * m) - n * C(m) - m * C(n);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            res -= (LL)2 * (gcd(i, j) - 1) * (n - i) * (m - j);
    cout << res << endl;
    return 0;
}