洛谷3166 [CQOI2014]数三角形

access_time    bookmark 题解    comment 0 条评论    省选/NOI-

题意

求由 $N\times M$ 的网络上三点构成的三角形个数。$N,M\le 1000$ 。

题解

图片来源于 https://www.luogu.org/blog/suwakow/solution-p3166

每个三角形都可以确定一个最小的包含它的矩形,称这种情况为完全覆盖。

1

那么可以把原矩形化为多个子矩形并只计算完全覆盖的情况。显然对于每个长宽相同的子矩形,它们对答案的贡献都是相同的,所以只用枚举长宽即可。

枚举子矩形长宽 $i\times j$ ,显然这样的子矩形有 $(n-i+1)\times (m-j+1)$ 个。下面对每个固定长宽的子矩形进行处理。

2

上图是个 $6\times 10$ 的矩形 $MNPQ$ ,设三角形为 $ABC$ 。

因为要求完全覆盖,所以 $ABC$ 三点至少有一个在端点上。不妨设 $A$ 一定在端点上。

当只有一个点在端点上时,剩下两点可以在除了端点的所有点上任意运动,个数为 $(i-1)\times (j-1)$ 。$A$ 所在的端点又有 $4$ 个,所以总个数为

$$4\times (i-1)\times (j-1) \tag{1}$$

当有两个点在端点上时,设另一个在端点的点为 $B$ ,对其进行讨论:

  1. 在 $N$ ,则 $C$ 在 $QP$ 间运动,贡献为 $i-1$
  2. 在 $Q$ ,贡献为 $j-1$
  3. 在 $P$ ,则 $C$ 在除了线段 $AP$ 上的所有节点都能构成三角形。贡献为 $(i+1)\times (j+1)-4-(\text{gcd}(i,j)-1)$

$-4$ 是因为不能放在端点;$\text{gcd}(i,j)-1$ 即为对角线上的节点个数,可以简单的证明:

设对角线上两点为 $(0,0)$ 和 $(i,j)$ ,那么对角线可以表示为

$$y=\dfrac{j}{i}\times x$$

在节点上就要求右边 $\in N^{\star}$ ,显然 $x=i-k\times \dfrac{i}{\text{gcd}(i,j)}$ 时满足,此时 $k\in [0,\text{gcd}(i,j)]$ ,再减去两个端点,所以有 $\text{gcd}(i,j)-1$ 个。

综上,两个端点时对答案的贡献为

$$(i-1)+(j-1)+(i+1)\times (j+1)-4-(\text{gcd}(i,j)-1)\tag{2}$$

当有三个点在端点时,对答案的贡献为

$$C_4^3=4\tag{3}$$

总的答案即为

$$(1)+(2)+(3)=6\times i\times j-2\times \text{gcd}(i,j)$$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m;

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

signed main()
{
    n=read(); m=read();
    ll ans=0;
    for (ll i=1;i<=n;i++)
        for (ll j=1;j<=m;j++)
            ans+=(n-i+1)*(m-j+1)*(6*i*j-2*gcd(i,j));
    return !printf("%lld",ans);
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。