[CQOI2014] 数三角形

给定一个 (n imes m) 的网格，请计算三点都在格点上的三角形共有多少个。(n,m leq 1000)

Solution

首先将 (n,m) 各 (+1) 转化为线数

用总数 (C_{nm}^3) 减去不合法的部分

处于竖直线上的共线情况 (mC_n^3)

处于水平线上的共线情况 (nC_m^3)

处于斜线上的共线情况 (sum_{i=1}^{n-1} sum_{j-1}^{m-1}2 (n-i)(m-j)((i,j)-1))

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n,m,ans;

signed main() {
    cin>>n>>m;
    n++; m++;
    ans=n*m*(n*m-1)*(n*m-2)/6;
    ans-=n*(n-1)*(n-2)*m/6;
    ans-=m*(m-1)*(m-2)*n/6;
    for(int i=1;i<n;i++) for(int j=1;j<m;j++) ans-=2*(n-i)*(m-j)*(__gcd(i,j)-1);
    cout<<ans;
}