洛谷3166 [CQOI2014]数三角形

题意

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

题解

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

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

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

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

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

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

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

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

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

在 $N$ ，则 $C$ 在 $QP$ 间运动，贡献为 $i-1$
在 $Q$ ，贡献为 $j-1$
在 $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);
}

题意

题解

新评论