本文主要是介绍数三角形（二）》-筛除法斜线结论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法思路：
1、一个直观的思路是筛除法，即：答案=总数-三点共线的种数
总数易求得，为组合数C((n+1)*(m+1),3)，考虑到n、m数值范围，考虑用long long。
2、三点共线的情况有：
（1）网格顶点同行，每行有m+1个顶点，共n+1行，共有：C(m+1,3) * (n+1)
（2）网格顶点同列，每列有n+1个顶点，共m+1列，共有：C(n+1,3) * (m+1)
（3）网格顶点同在斜线上，分斜向上和斜向下，显然两者方案数是一样的，下面考虑斜向下情况：
例如：n=5 m=7
（1）以行数为X、列数为Y的二维平面表示方格网络n*m，左上方格顶点为原点(0,0)。
（2）尝试从某网格顶点A朝斜向下方向的点B连斜线，不难总结出斜线结论：方格顶点A、B斜连线上有gcd(BC,AC)+1个点（BC、AC为A、B在X、Y轴的差，1≤AC≤m，1≤BC≤n）。
3、故而，对于斜向下的斜线，我们只需枚举两个方格顶点对(i,j)：两者满足在X轴、Y轴上分别相差i、j，可取定两端顶点，再在其间取一点构成三点共线，共有方案数为gcd(i,j)-1。易知，每个(i,j)点对都有(n-i+1) * (m-j+1)种，枚举(i,j)复杂度为O(n2n2)，gcd复杂度为O(n)。
4、如此，时间复杂度为O(n2n2lgn)，考虑到n的规模，可AC。
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
/*结论：对于二维n*m方格网，若AC//Y轴，BC//X轴，则斜线AB上有gcd(BC,AC)+1个方格顶点(1<=AC<=m 1<=BC<=n)。
对于斜线：可枚举X轴差为i、Y轴差j的两点，对该点对(i,j)取定两端点，则三点共线方案有gcd(i,j)-1，整个方格网有这样的点对(i,j)数为(n-i+1)*(m-j+1)，故总方案数=sum{(n-i+1)*(m-j+1)*(gcd(i,j)-1)} (1<=i<=n, 1<=j<=m)
枚举时间复杂度为O(n^2)，gcd(i,j)时间复杂度为lgn，总时间复杂度:O(n*nlgn)*/
const int N=3001;
typedef long long ll;
ll n,m,ans,sum;
ll calc(ll x){//计算组合数C(x,3)return x*(x-1)*(x-2)/6;
}int gcd(int x,int y){//最大公约数if(y==0) return x;return gcd(y,x%y);
}signed main(){cin>>n>>m;//n行m列ans=calc((n+1)*(m+1));//最多可构成三角形数(去掉任意三点共线的情况)ans-=(calc(n+1)*(m+1)+calc(m+1)*(n+1));//同列、同行三点共线种数for(int i=1;i<=n;i++)//枚举斜向下的斜线点对：(i,j) for(int j=1;j<=m;j++)sum+=(n-i+1)*(m-j+1)*(gcd(i,j)-1);ans-=sum*2;cout<<ans;
}这篇关于数三角形（二）》-筛除法斜线结论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
