BZOJ 3505 CQOI2014 數三角形 組合數學

BZOJ 3505 CQOI2014 數三角形 組合數學

題目大意：

給定一個m*n的方格，求上面有多少個格點三角形

m,n<=1000

枚舉O(m^3*n^3)，鐵定超時

我們選擇補集法

首先我們任意選擇三個不重復的點構成三角形 用組合數算出這一值 然後刨除三點一線的點即可

枚舉三點之中在兩邊的點的橫縱坐標之差，中間點的位置數為GCD(x,y)-1，統計答案即可

注意初始計算組合數時可能會爆int

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int m,n;
ll ans;
int GCD(int x,int y)
{
	if(!y)return x;
	return GCD(y,x%y);
}
int main()
{
	int i,j;
	cin>>m>>n;
	++m;++n;
	ans=m*n;
	ans=ans*(ans-1)*(ans-2)/6;
	for(i=0;i<=m;i++)
		for(j=0;j<=n;j++)
			if(i||j)
			{
				int gcd=GCD(i,j);
				ans-=(long long)(gcd-1)*(m-i)*(n-j)*(i&&j?2:1);
			}
	cout<