问题分析
可以先任意选(3)个数，然后减去三点共线的部分。
三点共线又分(2)种情况：
- 横的或者竖的。这一部分方案数是(n imes{mchoose 3}+m imes {nchoose3})。
- 斜的。不妨设线段一个端点在((1,1))，另一个端点在((i,j))，(i,j>1)。那么线段上的点总共有(gcd(i,j)+1)个点。所以一条这样的线段的贡献是(gcd(i,j)-1)。然后这样的线段共有((n-i+1) imes(m-j+1))条，然后由于对称还要乘以二。
参考程序
#include <cstdio>
long long C3( long long n ) {
return n * ( n - 1 ) * ( n - 2 ) / 6;
}
long long gcd( long long a, long long b ) {
long long m = a % b;
while( m ) {
a = b; b = m; m = a % b;
}
return b;
}
int main() {
long long n, m;
scanf( "%lld%lld", &n, &m ); ++n, ++m;
long long Ans = C3( n * m );
Ans -= n * C3( m ) + m * C3( n );
for( long long i = 2; i <= n; ++i )
for( long long j = 2; j <= m; ++j ) {
long long t = gcd( i - 1, j - 1 ) + 1;
if( t >= 3 )
Ans -= ( n - i + 1 ) * ( m - j + 1 ) * ( t - 2 ) * 2;
}
printf( "%lld
", Ans );
return 0;
}