Description

给出一个n*m的网格，求三点都在网格上的三角形有多少个 注意三角形三点不能共线 n,m<=1000

Analysis

正难则反，考虑用总的方案数减去三点共线方案数 如果三点在同一行或同一列很好算，如果三点是斜着的呢？ 画出一个矩形，那么矩形的两个对顶点跟对角线连线中间的格点可构成三点共线 对角线连线中间的格点数易证为gcd(x,y)，x,y分别为长和宽 而矩形有两条对角线，于是我们算出这样一个小矩形的方案数，然后再把这个矩形套进网格，乘上网格中这样的矩形数目 因此我们枚举长宽计算即可， O(n2logn)

Code

#include<cstdio> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; ll gcd(ll x,ll y) { if(x%y==0) return y; else return gcd(y,x%y); } int main() { ll n,m; scanf("%lld %lld",&n,&m);n++,m++; ll ans=n*m*(n*m-1)*(n*m-2)/6-m*n*(n-1)*(n-2)/6-n*m*(m-1)*(m-2)/6; fo(i,2,n-1) fo(j,2,m-1) ans-=2*(n-i)*(m-j)*(gcd(i,j)-1); printf("%lld",ans); return 0; }