Bzoj 3505(GCD+组合数)

BZOJ 3505
题意：见上。
先将m++, n++，因为格点数要多一个
我们可以先求出所有格点中选3个点的方案，即$C^{3}_{nm}$，然后就只用求出三点共线的三角形个数即可。
对于$k=0, k=INF$的三点共线三角形很好求，$C^{3}_{m} \cdot n + C^{3}_{n} \cdot m$
对于其他直线，我们可以枚举直线来求。枚举直线相当于枚举两个点。

结论：过$(x_1,y_1)$和$(x_2,y_2)$的直线整数顶点数为$gcd(\Delta x, \Delta y)-1$

根据这个性质，我们可以快速求解，但是还是要枚举两个点。我们发现过$(0,0)$点的直线可以平移得到其他直线，所以只用枚举一个点即可。

知识点：
1、正难则反思想
2、枚举直线相当于枚举两个点
3、过$(x_1,y_1)$和$(x_2,y_2)$的直线整数顶点数为$gcd(\Delta x, \Delta y)-1$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int m, n;
    LL ans;

    LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}

    void clean() {}
    int solve() {
        cin >> m >> n;
        clean();
        ++m, ++n;
        ans = (LL)(m * n) * (LL)(m * n - 1) * (LL)(m * n - 2) / 6ll;
        ans -= (LL)n * (LL)(n - 1) * (LL)(n - 2) * (LL)m / 6ll;
        ans -= (LL)m * (LL)(m - 1) * (LL)(m - 2) * (LL)n / 6ll;
        for (LL x = 1; x < n; ++x) 
        for (LL y = 1; y < m; ++y) {
            LL whw = gcd(x, y) - 1;
            if (whw < 0) whw = 0;
            //cout << whw << endl;
            ans -= whw * (n - x) * (m - y) * 2ll;
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}