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

点击量：208

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

目录

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