题目:Vasya and Triangle
题意:给出三个数n,m,k,求是否存在第一象限的3个点满足每个点的横坐标小于等于n,纵坐标小于等于m,坐标为整数,且构成的三角形面积等于n*m/k。
思路: 不妨把这个三角形看做直角三角形,然后把它补全成长方形,面积为nm2/k。 那么这个面积一定是整数,如果不是整数就输出NO。 接下来先尽量最大化横坐标x,即求gcd(nm2/k,n),然后算出y,输出即可。
代码:
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
ll n
,m
,k
;
ll
gcd(ll x
,ll y
) {
if(!y
) return x
;
return gcd(y
,x
%y
);
}
int main() {
scanf("%I64d%I64d%I64d",&n
,&m
,&k
);
if(n
*m
*2%k
) {
printf("NO");
return 0;
}
ll x
=gcd(n
*m
*2/k
,n
),y
=n
*m
*2/k
/x
;
if(y
>m
) x
*=2,y
/=2;
printf("YES\n");
printf("%I64d 0\n0 %I64d\n0 0",x
,y
);
return 0;
}