网格数三角形(Counting Triangles) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <numeric>
using namespace std;

long long C3(long long k) {
    if (k < 3) return 0;
    return k * (k - 1) * (k - 2) / 6;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, n;
    if (!(cin >> m >> n)) return 0;
    long long R = m + 1, C = n + 1;
    long long ans = C3(R * C) - R * C3(C) - C * C3(R);
    for (long long dx = 1; dx <= m; ++dx) {
        for (long long dy = 1; dy <= n; ++dy) {
            long long g = std::gcd(dx, dy) - 1;
            if (g > 0) {
                ans -= 2LL * (R - dx) * (C - dy) * g;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}