Codeforces 1058 D. Vasya and Triangle（分解因子）

题目：http://codeforces.com/contest/1058/problem/D

题意：有一个大小为N*M的矩阵内，构造一个三角形，使面积为(n*m)/k。若存在输出三个顶点（整数）。

分析：

首先可以判断，若(2*n*m)%k!=0，一定为NO。

其次，可以想到，三角形可以构造为一个顶点为（0,0）的直角三角形。且满足等式 (2*n*m)%k==0

如果k是偶数，那个k肯定可以和2约分，所以把k除2. 再得到tmp=gcd(n,k)，x=n/tmp，就是说能用n约掉一部分k就约掉，再用k/=tmp，y=m/k；

如果k是奇数，等式左边的2不能约掉，就要在经过和上面相同的操作后，把a * 2或者把b*2，肯定是有一个满足不超过限制的，因为之前a或b一定除了一个大于2的数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll gcd(ll x,ll y){
 5     if (y==0) return x;
 6     else return gcd(y,x%y);
 7 }
 8 int main(){
 9     ll n,m,k; cin >> n >> m >> k;
10     if (2*n*m%k) return cout << "NO
",0; 
11     int f=0;
12     if (k%2==0) k/=2; else f=1;
13     ll tmp=gcd(n,k); 
14     ll x=n/tmp; k/=tmp; ll y=m/k;
15     if (f){ 
16         if (x*2<n) x*=2; else y*=2;
17     }
18     cout << "YES
";
19     cout << 0 << " " << 0 << endl;
20     cout << x << " " << 0 << endl;
21     cout << 0 << " " << y << endl;
22     return 0;
23 }