题解 P3166 【[CQOI2014]数三角形】

PPL_ · 2019-11-14 20:51:15 · 题解

前言

今天测试考的这道题，但是扫雷把脑子扫炸了，于是没有推出来

我自闭了

本蒟蒻作者数学第一菜，可能说的不清楚，你有两个解决方案：

①憋着

②看别人的

题目

蒟蒻专用传送门

传送门(洛谷)

正题

我们别怕数学题，跟着我一步一步来，可以推出来的！

这道题总体思路是算出三角形的总数，减去共线的三角形个数，即为答案

首先它有多少个三角形呢？

明显是：C_{(n+1)*(m+1)}^3，即(n+1)*(m+1)个点中选3个点的方案数

为了方便处理，我们先减去 横线上 和 竖线上 的三点共线的三角形

一边有m+1和n+1个点，分别有n+1行，m+1列所以减去C_{n+1}^3*(m+1)和C_{m+1}^3*(n+1)

然后我们考虑斜着的三点共线的三角形，比如这个样子：

我们由于只有n^2的时间，就只能枚举一个点的坐标，根据它与原点的连线，确定线上有多少个坐标点

我们枚举了一个点，加上坐标原点，我们就确定了两个点了，还有一个点当然就是这条线段上的坐标为整数的点，现在我们就要算出有多少个这样的点(当然不算坐标原点和枚举的这个点)

首先已知坐标有(0,0)和枚举的(i,j)，那么这条直线的解析式为y=\frac{j}{i}x，因为这是一条线段，所以(0\le x\le i,0\le y\le j)，而且我们要排除(0,0)和(i,j)两个点，所以(0 < x < i,0 < y < j)，我们还要使y为整数，明显当i,j互质的时候已经没救了，所以i,j一定不互质

那么重新写这条直线的解析式：y=\frac{j/gcd(i,j)}{i/gcd(i,j)}x,(0 < x < i,0 < y < j)，现在这两个数(分子和分母)铁定互质了，我们只需要使x为i/gcd(i,j)的倍数就可以使y为整数了，那么有多少个x是i/gcd(i,j)的倍数呢？

我们回头看向x的范围(0 < x < i)，于是就有\frac{i}{i/gcd(i,j)}-1，即gcd(i,j)-1个，为什么要减一呢？给你几秒钟思考时间

因为是x < i而不是x \le i啊

于是我们求出有gcd(i,j)-1(1\le i\le n,1\le j\le m)个点在这个线段上(不算坐标原点和枚举的这个点)

我们把上面那个图拿下来验证：

但是坐标原点并不是一定在三角形上，而且我们已经花去了$O(n^2*log(n))$的时间了，这意味着我们只能在$O(1)$的时间内算出其它的方案数在草稿纸上一顿乱搞：我们可以把这个已经枚举出来的三角形向上或左平移，相当于就是其它位置的三点共线的三角形： ![](https://cdn.luogu.com.cn/upload/image_hosting/yct2rxk0.png) 红色的线段是我们枚举的，绿色的是向右平移，粉色(紫色？)的是向上平移的，当然，我们别忘了还有黑色的如上图所示，我们就可以计算出共有多少个可以通过平移得到的位置：$(n-i+1)*(m-j+1)

再乘上之前我们得出的gcd(i,j)-1，即(gcd(i,j)-1)*(n-i+1)*(m-j+1)个共线的三角形

完了吗？

naive

这只是从左下到右上的线段上的三角形，还有从左上到右下的线段上的三角形需要减：

如图，我们只减了形似于红色的线段上的三角形，但是还有形似于绿色的线段上的三角形

可以轻松证明，把它转一下，就是后者了，所以我们最后要乘个2

最后的最后，记得开long\space long

代码

//12252024832524
#include <cstdio>
#include <algorithm>
using namespace std; 

typedef long long LL;
const int MAXN = 1005;
int n,m,n1,m1;
LL s[MAXN][MAXN],ans;

int Read()
{
    int x = 0,f = 1;char c = getchar();
    while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
    return x * f;
}
void Put(LL x)
{
    if(x > 9) Put(x/10);
    putchar(x%10^48);
}
template <typename T>T Max(T x,T y){return x > y ? x : y;}
template <typename T>T Min(T x,T y){return x < y ? x : y;}
template <typename T>T Abs(T x){return x < 0 ? -x : x;}
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y);
}
LL Cn3(LL x)
{
    return x * (x-1) * (x-2) / 6;
}
void solve4()
{
    n = n1+1;
    m = m1+1; 
    ans = Cn3(n*m) - m*Cn3(n) - n*Cn3(m);
    for(int i = 1;i < n;++ i)
        for(int j = 1;j < m;++ j)
            ans -= 2ll * (gcd(i,j)-1) * (n - i) * (m - j);
    printf("%lld\n",ans);
}

int main()
{
//  freopen("triangle.in","r",stdin);
//  freopen("triangle.out","w",stdout);
    n1 = Read();
    m1 = Read();
    solve4();
    return 0;
}

By The Way

我再也不玩扫雷了，QAQ