Codeforces Round #512 Div. 2 D + 矩形三角形+gcd优化

题目链接：http://codeforces.com/contest/1058/problem/D
题目大意：输入n， m，k，如果能够为n， 宽为m的矩形中找到三个点，这三个点形成的三角形的面积为(n*m)/k，如果能。输出YES并且输出三个点的坐标。如果不能输出NO。

思路：首先可以证明：在矩形中的三角形都可以转化成底边在x轴，高在y轴的直角三角形
ab/2=nm/k
因为0<=a<=n，0<=b<=m
所以k>=2并且(ab=2nm)%k==0那么就一定能够找到这样的三角形。
假如s=(2nm)，那么我们要找到a，b;
因为1≤n,m≤1e9，当时这里没有优化好，用了纯暴力枚举，T了。

优化：因为a<=n， b<=m;
所以在枚举a时希望满足条件（a<=n）的a值尽量大，这样b尽量小。b就取得最小值。如果最小的b值都>m，那么就枚举满足条件（b<=n）的b值尽量大。因为一定能够找到这样的三角形。所以其中一个一定满足。

现在就是怎么快速找到满足条件（a<=n）的a的最大值。这个时候a<=n，因为b=s/a；b为整数，那么s%a== 0.
如果循环枚举a。那么复杂度O（n），n<=10^9。
因为s=2nm所以s%n==0，因为s%a并且a<=n，所以n%a ==0。

那么条件为s%a ==0。n%a ==0并且a<=n。
所以a=gcd（n，s）。

思考：gcd真是个好东西。用的很巧妙

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

int main()
{
    long long n, m, k;
    long long s;
    long long s1;
    long long s2;
    scanf("%lld%lld%lld",&n,&m,&k);
    s=n*m*2;
    if(s%k==0&&k>=2)
    {
        printf("YES\n");
        s/=k;
        long long a, b;

        long long m1=__gcd(s, n);
        long long m2=__gcd(s, m);

        if(s/m1<=m)
            a=m1, b=s/m1;
        else if(s/m2<=n)
            a=s/m2, b=m2;

        printf("0 0\n");
        printf("%lld 0\n",a);
        printf("0 %lld\n",b);
    }
    else
        printf("NO\n");

    return 0;
}