Вася и треугольник

Удвоенная площадь треугольника, углы которого лежат в целочисленных точках всегда целочисленна. Поэтому если 2𝑛𝑚
 не делится на 𝑘
, то невозможно найти подходящий треугольник.

Иначе всегда можно найти подходящий треугольник. Для этого сначала разделим 𝑘
 на 2
, если он четно. После это найдем 𝑔=gcd(𝑘,𝑛)
, где gcd(𝑥,𝑦)
 — наибольший общий делитель чисел 𝑥
 и 𝑦
. Обозначим 𝑘 ′=𝑘𝑔
 и запомним длину первой стороны треугольника — число 𝑎=𝑛𝑔
. Затем запомним длину второй стороны треугольника — число 𝑏=𝑚𝑘 ′
. Теперь, если в начале мы не делили 𝑘
 на 2
, нам нужно домножить одну из сторон 𝑎
 или 𝑏
 на 2. Домножим 𝑎
 на 2, если она меньше 𝑛
, иначе домножим 𝑏
 на 2. Заметим, что если 𝑎=𝑛
, то 𝑏
 обязательно будет меньше 𝑚
.

После этого ответ найден — треугольник в точках (0,0),(𝑎,0),(0,𝑏)
. Нетрудно убедиться, что его площадь равна 𝑛𝑚𝑘
.

#include<bits/stdc++.h>

using namespace std;

long long gcd(long long a, long long b){
    return a? gcd(b % a, a) : b;
}

int main() {
    //freopen("input.txt", "r", stdin);

    long long n, m, k;
    cin >> n >> m >> k;

    bool isEven = k % 2 == 0;
    long long p = n * m;
    if(isEven) k /= 2;

    if(p % k != 0){
        cout << "NO" << endl;
        return 0;
    }

    long long x = gcd(n, k);
    k /= x;
    long long a = n / x;

    x = gcd(m, k);
    k /= x;
    assert(k == 1);
    long long b = m / x;


    if(!isEven){
        if(a < n)
            a += a;
        else{
            assert(b < m);
            b += b;
        }
    }

    cout << "YES" << endl;
    cout << "0 0\n";
    cout << 0 << ' ' << b << endl;
    cout << a << ' ' << 0 << endl;

    return 0;
}