文章目录

D- Vasya and Triangle

题目链接：http://codeforces.com/contest/1030/problem/D
题意：给一个 N × M N \times M N×M的范围，和一个 K K K，求一个三角形的面积为 N × M K \frac{N \times M}{K} KN×M​，输出三角形的三个顶点坐标

转化一哈题意就是给出矩形的面积，求满足范围的矩形的两边

一个暴力的思路就是枚举矩形的一条边，但是直接枚举是不行的，我们阔以分析出来，最多只用枚举到 S \sqrt{S} S ​,因为面积一定的时候，矩形的两条边最大不会超过 S \sqrt{S} S ​ 的

然后就是从多少开始枚举，我们枚举的这条边是从小到大的，那么另外一条边就是从大到小的，所以，考虑另外一条边最大的时候，也就是我们枚举的这条边最小的时候，就是 S m a x ( a , b ) \frac{S}{max(a,b)} max(a,b)S​

1.暴力做法

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int main()
{
	LL N,M,K;
	while(cin>>N>>M>>K)
	{
		LL x=-1,y=-1;
		if(2LL*N*M%K)cout<<"NO"<<endl;
		else
		{
			LL x=-1,y=-1;
			LL area=2LL*N*M/K;
			for(LL i=max(1LL,area/max(N,M)); i*i<=area; i++)
			{
				if(area%i==0)
				{

					if(i<=N&&area/i<=M)
					{
						x=i,y=area/i;
						break;
					}
					else if(area/i<=N&&i<=M)
					{
						x=area/i,y=i;
						break;
					}
				}
			}
			cout<<"YES"<<endl;
			cout<<"0 0"<<endl;
			cout<<"0 "<<y<<endl;
			cout<<x<<" 0"<<endl;
		}
	}
}

2.O(log)做法

然后还有一种 O ( l o g ) O(log) O(log)的思路，很牛批，参考这位同学的：https://blog.csdn.net/rabbit_zar/article/details/82827582

就是找出一条边在范围内满足条件的最大值

比如这条边的范围是 n n n以内，然后又要被 S S S 出的尽，那不就是求 g c d ( n , S ) gcd(n,S) gcd(n,S) 么？
可是还有点不理解的地方就是，要是另外一条边不满足条件，求出的最大值x可能还要乘以2是为什么喃？？？

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int main()
{
	LL N,M,K;
	while(cin>>N>>M>>K)
	{
		LL x=-1,y=-1;
		if(2LL*N*M%K)cout<<"NO"<<endl;
		else
		{
			LL x=-1,y=-1,area=2LL*N*M/K;
			x=__gcd(area,N);//这一步是关键的一步，使横坐标最大
			y=area/x;
			if(y>M)x<<=1,y>>=1;//为啥还不是最大值喃？ 
			cout<<"YES"<<endl;
			cout<<"0 0"<<endl;
			cout<<"0 "<<y<<endl;
			cout<<x<<" 0"<<endl;
		}
	}
}