D. Vasya and Triangle

Description:

Vasya has got three integers n n n, m m m and k k k. He’d like to find three integer points ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​), ( x 2 , y 2 ) (x_2, y_2) (x2​,y2​), ( x 3 , y 3 ) (x_3, y_3) (x3​,y3​), such that 0 ≤ x 1 , x 2 , x 3 ≤ n 0 \le x_1, x_2, x_3 \le n 0≤x1​,x2​,x3​≤n, 0 ≤ y 1 , y 2 , y 3 ≤ m 0 \le y_1, y_2, y_3 \le m 0≤y1​,y2​,y3​≤m and the area of the triangle formed by these points is equal to n m k \frac{nm}{k} knm​.
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 n n, m m m, k k k ( 1 ≤ n , m ≤ 1 0 9 1\le n, m \le 10^9 1≤n,m≤109, 2 ≤ k ≤ 1 0 9 2 \le k \le 10^9 2≤k≤109).

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 x_i, y_i xi​,yi​ — 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).

Sample Input:

4 3 3

Sample Output:

YES
1 0
2 3
4 1

Sample Input:

4 4 7

Sample Output:

NO

题目链接

在 x ∈ [ 0 , n ] , y ∈ [ 0 , m ] x\in[0,n],y\in[0,m] x∈[0,n],y∈[0,m] 的范围内找出三个整数点使得所构成三角形面积为 n m k \frac{nm}{k} knm​

整数顶点构成的三角形可以用一个平行坐标轴的矩形严格包围，利用增补法计算三角形的面积

此图: S △ A E F = S □ A B C D − S △ A D E − S △ C E F − S △ A B F \mathcal{S}\bigtriangleup AEF=\mathcal{S}\Box ABCD -\mathcal{S}\bigtriangleup ADE-\mathcal{S}\bigtriangleup CEF-\mathcal{S}\bigtriangleup ABF S△AEF=S□ABCD−S△ADE−S△CEF−S△ABF

其中 S □ A B C D \mathcal{S}\Box ABCD S□ABCD 一定为整数，而其减去的三个三角形面积为整数或整数的一半，所以 S △ A E F \mathcal{S}\bigtriangleup AEF S△AEF 一定等于 x 2 \frac{x}{2} 2x​

对题目给出 n m k \frac{nm}{k} knm​ 进行约分，根据上述性质 k k k 仅可能有 1 、 2 1、2 1、2 两种结果，其余情况均判定为无解

在有解的情况下所有合法面积均可用由两坐标轴构成的直角三角形组成（具体证明移步题解 CF1030D 【Vasya and Triangle】），这样三点的形式就可以确定下来 ( 0 , 0 ) 、 ( x , 0 ) 、 ( 0 , y ) (0,0)、(x,0)、(0,y) (0,0)、(x,0)、(0,y)

根据三角形面积关系可得等式
x y 2 = n m k \frac{xy}{2}=\frac{nm}{k} 2xy​=knm​
化简得
x y = 2 n m k xy=\frac{2nm}{k} xy=k2nm​
这样根据等式关系可构造出 x 、 y x、y x、y 的值

令 x = 2 n , y = m k x=2n,y=\frac{m}{k} x=2n,y=km​ 并约分得 x = 2 n gcd ⁡ ( 2 n , k ) , y = m k gcd ⁡ ( 2 n , k ) x=\frac{2n}{\gcd(2n,k)},y=\frac{m}{\frac{k}{\gcd(2n,k)}} x=gcd(2n,k)2n​,y=gcd(2n,k)k​m​

因为三角形顶点横纵坐标有范围限制，所以如果结果中 x > n x>n x>n

则可令 x = n k , y = 2 m x=\frac{n}{k},y=2m x=kn​,y=2m 并约分得 x = n k gcd ⁡ ( 2 m , k ) , y = 2 m gcd ⁡ ( 2 m , k ) x=\frac{n}{\frac{k}{\gcd(2m,k)}},y=\frac{2m}{\gcd(2m,k)} x=gcd(2m,k)k​n​,y=gcd(2m,k)2m​

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M;
ll K;
ll X, Y;

int main(int argc, char *argv[]) {
    scanf("%lld%lld%lld", &N, &M, &K);
    if (K / __gcd(N * M, K) > 2) {
        printf("NO\n");
        return 0;
    }
    printf("YES\n");
    printf("0 0\n");
    X = 2 * N / __gcd(2 * N, K);
    Y = M / (K / __gcd(2 * N, K));
    if (X > N) {
        Y = 2 * M / __gcd(2 * M, K);
        X = N / (K / __gcd(2 * M, K));
    }
    printf("%lld 0\n", X);
    printf("0 %lld\n", Y);
    return 0;
}