数三角形

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1437 字
给定n×m的网格，统计三个顶点都在格点上且不
一本通
练习
正文

/*
原题：T1655「一本通 6.6 练习 4」数三角形
题意：给定 n×m 的网格，统计三个顶点都在格点上且不共线的三角形的个数。
思路：先算出所有三点组 C(P,3)（P 为格点总数），再减去三点共线的情况。
共线按方向分类：水平按行算、竖直按列算；斜方向只对互素的步长 (dx,dy) 统计，
每个方向只需枚举那些"再退一步就出界"的起点（x<dx 或 y<dy），沿方向数出
该直线上格点数 L，累减 C(L,3)；正负斜率对称，故结果乘 2。
复杂度：与网格规模正交比有关，主要枚举互素方向与起点，空间 O(1)
易错点：1) 格点数是 (n+1)·(m+1) 而不是 n·m，别少算一圈点；
2) 斜方向步长必须互素，否则同一条直线会被重复统计；
3) 起点条件为 x<dx 或 y<dy，漏写会把同一条直线当成多条。
*/
#include <bits/stdc++.h>
using namespace std;
long long C3(long long v){
    if(v<3){
        return 0;
    }
    return v*(v-1)*(v-2)/6;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long n,m;
    cin>>n>>m;
    long long X=n+1;
    long long Y=m+1;
    long long bad=0;
    bad+=Y*C3(X);
    bad+=X*C3(Y);
    for(long long dx=1;dx<X;dx++){
        for(long long dy=1;dy<Y;dy++){
            if(std::gcd(dx,dy)!=1){
                continue;
            }
            long long cur=0;
            for(long long x=0;x<X;x++){
                long long ylim=(x<dx)?Y-1:dy-1;
                for(long long y=0;y<=ylim;y++){
                    long long len=0;
                    long long cx=x;
                    long long cy=y;
                    while(cx<X && cy<Y){
                        len++;
                        cx+=dx;
                        cy+=dy;
                    }
                    cur+=C3(len);
                }
            }
            bad+=2*cur;
        }
    }
    cout<<C3(X*Y)-bad<<"\n";
    return 0;
}
数三角形

正文

一本通·提高篇的其它内容
