CF1030D Vasya and Triangle 题解【数学】【gcd】【解析几何】

作者: wjyyy 分类: Codeforces,gcd/lcm,数学,解析几何,解题报告 发布时间: 2018-09-25 16:33

点击量:33

 

    考试的时候看出来了一个比较重要的结论就写出来了……

 

Description

Vasya has got three integers \(n,m\) and \(k\). He’d like to find three integer points \((x1,y1),(x2,y2),(x3,y3)\), such that \(0≤x1,x2,x3≤n,0≤y1,y2,y3≤m\) and the area of the triangle formed by these points is equal to \(\frac{nm}k\).

Help Vasya! Find such points (if it’s possible). If there are multiple solutions, print any of them.

Input

The single line contains three integers \(n,m,k(1\le n,m\le 10^9,2\le k\le 10^9)\).

Output

If there are no such points, print “NO“.

Otherwise print “YES” in the first line. The next three lines should contain integers \(x_i,y_i\)— coordinates of the points, one point per line. If there are multiple solutions, print any of them.

You can print each letter in any case (upper or lower).

Examples

input

4 3 3
output
YES
1 0
2 3
4 1
input
4 4 7
output
NO

Note

In the first example area of the triangle should be equal to \(\frac{nm}k=4\). The triangle mentioned in the output is pictured below:

In the second example there is no triangle with area \(\frac{nm}k=\frac{16}7\).

题意:

    在\(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\),但是多出来的只是一个\(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)//枚举下界注意会出现0
        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;
}

说点什么

avatar
  Subscribe  
提醒
/* */