当前位置：网站首页>P3166数三角形（容斥+gcd）

P3166数三角形（容斥+gcd）

2022-07-19 01:50:00 【to cling】

Problem

给定一个 $N\times M$ 的网格，请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

Solution

对于网格中的两个点，设其横纵坐标之差分别为：i，j
则这两个点连线上的整数格点的个数为： $g c d (i, j) - 1$
证明：两点（0，0）和（6， 9）的横纵坐标之差为（6， 9）。
则点（2， 3），（4， 6），（6， 9）这三个点都在这两个点的连线上。
（由该结论可知：如果两个点坐标之差（i，j）的最大公约数为1，则其连线上无整数格点）

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;
}

版权声明
本文为[to cling]所创，转载请带上原文链接，感谢
https://blog.csdn.net/QQ2530063577/article/details/125666704

边栏推荐

猜你喜欢

随机推荐