思路

选任意不同的三个点方案数为.
然后需要减去共线的三个点的方案数.
首先横纵方向.
然后考虑枚举每个向量(也就是斜率和长度相同的线段同时枚举),该向量起始位置和中间的某个点为一种方案,那么对于向量,贡献为.上下翻转也是可行的,贡献再乘2.
这样子复杂度就是.

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL C3( LL x ){ return x * ( x - 1 ) * ( x - 2 ) / 6; }
LL gcd( LL x, LL y ){ return y ? gcd( y, x % y ) : x; }

int N, M;
LL ans;

int main(){
    scanf( "%d%d", &N, &M ); ++N; ++M;
    ans = C3( N * M ) - C3( N ) * M - C3( M ) * N;
    for ( int i = 1; i < N; ++i )
        for ( int j = 1; j < M; ++j )
            ans -= ( gcd( i, j ) - 1 ) * ( N - i ) * ( M - j ) * 2;
    printf( "%lld\n", ans );
    return 0;
}