[CQOI2014]数三角形

题意

给定一个(n*m)的网格，计算三点都在格点上的三角形共有多少个（显然三点不能共线）

思路

答案显然为全集-不满足条件的三角形

全集为(C(n*m,3))

横行/竖行：(C(m,3)*n+C(n,3)*m)

本题难点在于怎么处理斜行

一条斜边可以由一条横边+一条竖边表示，所以枚举竖边和横边的长度就好了，一类斜边((i*x+j*y))的贡献为((n-i)*(m-j)*(gcd(i,j)-1)*2)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll ans=0;
int gcd(int x,int y) {return (!y) ? x : gcd(y,x%y);}
int main()
{
	cin>>n>>m;
	++n; ++m;
	ans=(n*m) * (n*m-1) * (n*m-2)/6;
	ans-=(n) * (n-1) * (n-2) /6 * m;
	ans-=(m) * (m-1) * (m-2) /6 * 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;
}