题解 CF1030D 【Vasya and Triangle】

wjyyy · 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;
}