题解 CF1030D 【Vasya and Triangle】
da32s1da
2018-12-15 08:56:37
首先，有结论：
$$\text{(0,0),(x,0),(0,y)}\ ,1\le x\le n,1\le y\le m \ \text{可表示出}\frac{1}{2}\text{到}\frac{n\times m}{2}\text{之间的所有的}\frac{z}{2}\ ,1\le z\le n\times m$$
证明显然。
令$x=1,y=1...m$，表示$\frac{1}{2}\ .\ .\ .\ \frac{m}{2}$。
令$x=2,y=1...m$，表示$(2\times \frac{1}{2})\ .\ .\ .\ (2\times \frac{m}{2})$。
令$x=3,y=1...m$，表示$(3\times \frac{1}{2})\ .\ .\ .\ (3\times \frac{m}{2})$。
$....$
令$x=n,y=1...m$，表示$(n\times \frac{1}{2})\ .\ .\ .\ (n\times \frac{m}{2})$。
综上。
回到本题。由于是端点三角形，我们知道面积肯定是$\frac{z}{2}\ ,1\le z\le n\times m$。
于是判掉无解。
此时答案是$\frac{x\times y}{2}=\frac{n\times m}{k}=\frac{\frac{2\times n\times m}{k}}{2}$。
故$x\times y=\frac{2\times n\times m}{k}$。
因为$x,y$都是整数，且$1\le x\le n\ ,1\le y\le m$，所以我们令$x=\frac{2n}{\gcd(2n,k)},y=\frac{m}{\frac{k}{\gcd(2n,k)}}$。
但此时$x$可能大于$n$，此时$x$一定是$2$的倍数。我们让$x=\frac{x}{2}\ ,y=2y$。此时一定满足$1\le x\le n\ ,1\le y\le m$，输出即可。
```
#include<cstdio>
typedef long long LL;
LL n,m,k,X,Y;
LL gcd(LL u,LL v){return v?gcd(v,u%v):u;}
int main(){
scanf("%I64d%I64d%I64d",&n,&m,&k);
if(k/gcd(n*m,k)>2){//特判无解
puts("NO");
return 0;
}
puts("YES");
printf("0 0\n");//原点
X=(2*n)/gcd(2*n,k);
if(X>n)X/=2,m*=2;//调整解
k/=gcd(2*n,k);
Y=m/k;
printf("%I64d 0\n",X);
printf("0 %I64d\n",Y);
}
```