3505: [Cqoi2014]数三角形
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。
注意三角形的三点不能共线。
1<=m,n<=1000
$n++ m++$
$ans={nm\choose 3}-n*{m\choose 3}-m*{n\choose 3}-斜线上的情况$
n和m很小，我们直接枚举以(0,0)为左端点的斜线，以两端点为两个点，中间的第三个点有$(x,y)-1$种选择，然后乘上平移的方案数再乘以2，斜线还有反向
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
ll n,m,ans;
int gcd(int a,int b){return b==?a:gcd(b,a%b);}
int main(){
n=read()+;m=read()+;
ll x=n*m;
ans+=x*(x-)*(x-)/;
ans-=m*n*(n-)*(n-)/+n*m*(m-)*(m-)/;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
ans-=(n-i)*(m-j)*(gcd(i,j)-)<<;
printf("%lld",ans);
}