Technocup 2019 - Elimination Round 1 D. Vasya and Triangle

题目链接：https://codeforces.com/problemset/problem/1030/D
题目大意：
Vasya这个小鬼有三个数n,m,k, 他想找到三个整点(x1, y1), (x2, y2), (x3, y3)，其中0 <= x1, x2, x3 <= n, 0 <= y1, y2, y3 <= m，使得这三个点组成的三角形面积等于mn / k。这个死仔包不会做，就把问题丢给你了。

解题思路：
首先你得知道由整点组成的三角形面积肯定是个整数。可以由向量的外积证明（具体就是计算一个行列式的值，由于x和y都是整数，结果必为整数）。换句话说，2mn/k也必为整数，若2mn%k != 0，没有这样的三角形，否则进入下一步构造。
不妨假设这个三角形是个直角三角形，一个顶点在(0, 0)。余二定点坐标设为(a, 0), (0, b)。怎么构造这两个a和b呢？我们发现2mn/k的分母k在分子m和n作用下必然是会给约掉的。如果gcd(2n, k) == 1, gcd(2m, k) >= 2那就令b = 2m / gcd(2m, k), a = 2mn / (kb), 如此构造不难得出b <= m, a == n。否则，令g = gcd(2n, k), a = 2n / g, b = m*g / k. (b一定是整数)

代码如下：

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll n, m, k;

int main(){
    std::ios::sync_with_stdio(false);
    while(cin >> n >> m >> k){
        if(2*m*n % k != 0){
            cout << "NO" << endl;
            continue;
        } else {
            cout << "YES" << endl;
            ll g = __gcd(2*n, k);
            if(g == 1){  //如果g == 1那么__gcd(2*m, k) == k
                cout << "0 0" << endl;
                cout << n << " 0" << endl;
                cout << "0 " << 2*m / k << endl;
            } else {     //否则套公式
                cout << "0 0" << endl;
                cout << "0 " << m*g / k << endl;
                cout << 2*n/g << " 0" << endl;
            }
        }
    }

    return 0;
}