[CQOI2014]数三角形

一时失言乱红尘 2022-01-08 00:23 208阅读 0赞

[\[CQOI2014\]数三角形][CQOI2014]

给定\\(n\\times m\\)的网格，求三个点在其格点上的三角形个数，1<=m,n<=1000。

### 解 ###

#### 法一：直接 ####

显然为组合计数问题，关键在于划分问题，注意到一个三角形必然会被一个最小的矩形所限制，于是可以以矩形来划分，而现在问题变成对一个矩形内最大的三角形的方案数，显然最大三角形关键在于三角形顶点与矩形顶点之间的关系。

设有一\\(a\\times b\\)矩形，有

1： 三角形有一个顶点在矩形顶点上，有4个矩形顶点可以选择，其余两个三角形顶点可以在剩余两条边自由移动，即\\(4\\times (a-1)\\times (b-1)\\)。

2：三角形有两个顶点在矩形同边顶点上，显然可以旋转4次，剩下一个三角顶点可以自由在一条边上移动，即\\(2\\times(a-1)+2\\times(b-1)\\)。

3：三角形有两个顶点在矩形对角顶点，此时该点能自由移动，只是不能在对角线上，

--------------------

引理：对角线上的整点个数为gcd(a,b)+1

证明：

对于对角线上最靠近原点（0,0）的点（x,y），对角线上最靠近（x，y）的点必然是（2x，2y），依次类推，于是我们得知x，y必然是互质的，而取得gcd（a，b）即x，y前的系数，也就是除了原点之外的点，故加1及所需。

--------------------

不难得知方案数应为\\((a\\times b-gcd(a,b)-1)\\times 2\\)

4：三角形有三个顶点在矩形对角顶点，显然讨论3已经包含了这种情况，故无需再考虑。

综上所诉，

\\\[ans=(n-a+1)\\times(n-b+1)\\times\[4\\times (a-1)\\times (b-1)+\\\]

\\\[2\\times(a+b-2)+(a\\times b-gcd(a,b)-1)\\times 2\]\\\]

枚举计算答案即可。

##### 参考代码： #####

#include <iostream> #include <cstdio> #define il inline #define ri register #define ll long long using namespace std; il int gcd(int,int); int main(){ int m,n; scanf("%d%d",&m,&n); ri int i,j;ri ll ans(0); for(i=1;i<=m;++i) for(j=1;j<=n;++j) ans+=(ll)(6*i*j-2*gcd(i,j))*(m+1-i)*(n+1-j); printf("%lld",ans); return 0; } il int gcd(int x,int y){ return x%y?gcd(y,x%y):y; }

#### 法二：补集 ####

注意到直接做不好做，于是考虑补集，我们能很轻松求出不限制为三角形的方案数，于是我们考虑不是三角形的方案数，显然在一条直线上，于是考虑枚举直线，而这样我们没办法枚举唯一的斜率，这样会导致重复，于是考虑枚举线段，这样就确定了两个端点，另一个点必然在线段内，而方案数由法一的引理不难得出点数，再将该条线段平移加对称操作，枚举减总方案去即可,但是注意竖直和水平的直线，我们得额外减去其方案数。

所以

\\\[ans=C\_\{nm\}^3-\\sum\_\{i=1\}^n\\sum\_\{j=1\}^m2\\times (gcd(i,j)-1)\\times (n-i+1)\\\]  
\\\[\\times(m-j+1)-m\\times C\_n^3-n\\times C\_m^3\\\]

参考代码：

#include <iostream> #include <cstdio> #define il inline #define ri register #define ll long long #define swap(x,y) x^=y^=x^=y using namespace std; il int gcd(int,int); int main(){ int n,m,i,j;ll ans; scanf("%d%d",&n,&m),ans=(n+1)*(m+1); ans*=(ans-1)*(ans-2),(ans/=3)/=2; for(i=1;i<=n;++i) for(j=1;j<=m;++j) ans-=(gcd(i,j)-1)*(n-i+1)*(m-j+1)<<1; ans-=(n+1)*n*(n-1)/3/2*(ll)(m+1),ans-=(m+1)*m*(m-1)/3/2*(ll)(n+1); printf("%lld",ans); return 0; } il int gcd(int a,int b){ while(b)swap(a,b),b%=a;return a; }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10785740.html

[CQOI2014]: https://www.luogu.org/problemnew/show/P3166