题解 CF1030D 【Vasya and Triangle】

2018-09-25 16:37:21


在我的blog里看

题意:

在$n\times m$的矩形中找出一个格点三角形,使得$S_\triangle=\frac{nm}k,k\ge 2$。

题解:

首先这个题要求出在$n\times m$的矩形中,是否存在一个格点三角形,使得这个格点三角形的面积为$\frac{nm}k$。

如果我们直接构造,可能需要枚举的东西太多了,$n,m,k$都达到了$10^9$的数量级。但是我们可以发现题目中$k$一定$\ge 2$,那么如果能构造,就一定可以被装在这个$n\times m$的矩形中。因为$n\times m$的矩形最大可以装下$\frac{nm}2$的三角形。此时问题转化为能否构造出一个$\frac{nm}k$的格点三角形,注意这个题还需要输出顶点方案

样例给出了一个合法的数据和一个不合法的数据,一开始感觉上下互质可能会出问题,但是这个题和质数貌似没有关系。但是和约分肯定有关,因此猜想:格点三角形的面积一定是$\frac 12$的倍数。也就是说,$\frac {nm}k$约分后,分母不是$1$就是$2$。

既然是三角形,由于初中老师教过割补法求平面直角坐标系中三角形的面积,那我们就证一下这个猜想。我们构造一个任意的格点三角形,那么这个格点三角形的面积可以表示为一个边与坐标轴平行的矩形,减去三个直角三角形,这三个直角三角形都满足直角边与坐标轴平行。

这个矩形的面积是一个整数,则三角形的面积为$S_\triangle=\frac{ab}2$。又因为在格点三角形中,$ab$是整数,所以$S_\triangle$一定是$\frac 12$的倍数。

证完这个东西,我们发现三角形就是可构造的了。设要求的三角形面积为$S=\frac t2,t\in \mathbb N^*$,那么我们只需要在这个$n\times m$的三角形中找出$a\le n,b\le m$使得$ab=2S=t$即可,此时$t$并不会爆long long。那么一定存在这样一组整数对$(a,b)$吗?答案是肯定的。

要证存在整数对$(a,b)\ \mathrm{St.}\ ab=\frac{2nm}{k},a\le n,b\le m$,且$\gcd(2nm,k)=k,k\ge 2$。那么由于$\gcd(2nm,k)=k$,除出来的结果是整数,不考虑分子上的$2$,则这个整数应该只含$n,m$的质因子,且$ab\le nm$。

单独讨论分子上的$2$

  • 如果满足$k|2$,则这个整数满足“只含$n,m$的质因子”,并且$ab\le nm$;

  • 如果$k\not|2$,则$k\ge 3$,但是满足$\gcd(2nm,k)=k$,可知$\frac{2nm}k<nm$,同时$k|nm$,让$ab=\frac 2k\cdot nm$,约掉之后就可以使$n$或$m$中至少一个减小。比方说$k=p_1p_2$,则$ab=2\cdot \frac {n}{p_1}\cdot \frac{m}{p_2}$,则$ab\le nm$。又因为$p_1\ge 2$或$p_2\ge 2$,且$ \frac {n}{p_1},\frac{m}{p_2}$都是整数,因此$p_1,p_2$中至少有一个满足$\frac{2n}{p_1}\le n$或$\frac {2m}{p_2}\le m$。虽然不一定满足“只含$n,m$的质因子”,但是多出来的只是一个$2$,它可以被$\frac 2k$中的$k$约掉,从而达到上一句话的情况,就可以用$a,b$来表示了。

    最后需要得出答案,构造出一个直角三角形,直角边分别为$a,b$,如何枚举$(a,b)$呢?作为$S'=\frac{2nm}k$的约数,它的枚举复杂度为$\sqrt{S'}$,数量级是$10^9$,从$1$开始容易$TLE$,事实上良心的pretest10也卡掉了我的前两次提交。因为$a\le n,b\le m$,所以枚举起点应该在$\lfloor \frac{S'}{\max(n,m)}\rfloor$,以避免枚举“另一条边超过$\max(n,m)$”的情况。不过最后还是要稍微检验一下(防止写快了弄混……

    其实只要推出来面积一定是$\frac 12$的倍数,和最后一段的上下界优化就可以做题了。但是为了严谨和题解需要我还是证明了一下存在性……

Code:

#include<cstdio>
#include<cstring>
#include<cmath>
long long n,m,k;
long long gcd(long long a,long long b)
{
    if(!b)
        return a;
    return gcd(b,a%b);
}
int main()
{
    scanf("%I64d%I64d%I64d",&n,&m,&k);
    long long tt=n>m?n:m;
    int flag=(n>=m);
    k=k;
    long long t=n>m?n:m;
    n=n*m;
    long long tmp=gcd(n,k);
    n/=tmp;
    k/=tmp;
    if(k>2)
    {
        puts("NO");
        return 0;
    }
    if(k==1)
        n*=2;
    long long up=sqrt(n)+1;
    for(int i=(n/tt)?(n/tt):1;i<=up;++i)
        if(n%i==0)
            if(n/i<=t)
            {
                n=n/i;
                m=i;
                break;
            }
    puts("YES");
    puts("0 0");
    if(flag)
    {
        printf("%I64d 0\n",n);
        printf("0 %I64d\n",m);
    }
    else
    {
        printf("%I64d 0\n",m);
        printf("0 %I64d\n",n);
    }
    return 0;
}