P3166 number triangle (tolerance and exclusion +gcd)

Problem

Given a $N\times M$ The grid of , Please calculate the total number of triangles with three points on the grid . Note that the three points of a triangle cannot be collinear .

Solution

1. For two points in the grid , Let the difference between the horizontal and vertical coordinates be ：i,j
   Then the number of integer lattice points on the line between these two points is ： $gcd(i,j)-1$
   prove ： At two o 'clock （0,0） and （6, 9） The difference between the horizontal and vertical coordinates of is （6, 9）.
   The point of （2, 3）,（4, 6）,（6, 9） These three points are on the line between these two points .
   （ According to this conclusion ： If the difference between the coordinates of two points （i,j） The greatest common divisor of is 1, Then there is no integer lattice on its line ）
   

Code

int gcd(int a, int b)
{
    
	if (!b) return a;
	return gcd(b, a % b);
}

ll C(ll x)
{
    
	return x * (x - 1) * (x - 2) / 6;
}

int main()
{
    
	IOS;
	ll n, m;
	cin >> n >> m;
	n++; m++;
	ll ans = C(n * m);
	ans -= n * C(m) + m * C(n);
	
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			ans -= (n - i) * (m - j) * (gcd(i, j) - 1) * 2;

	cout << ans << endl;


	return 0;
}