[几何][数学][思维] CF 1030D Vasya and Triangle

题意:给定n,m,k,要求在横坐标小于n纵坐标小于m的整点中找到一个三角形使得三角形面积为 n*m/k。一开始一直纠结于存在性。首先可以证明如果2*n*m%k!=0那么一定是NO。当满足这一条件的时候,可以把n*m/k上下拆分,把k拆成gcd(n,k)*(k/gcd(n,k)),然后上下约分就可得到一组ab,这时候如果后者和m不能完全约分说明分母里会剩下一个2(因为分子上*2是可以完全约分的),这时候ab就是答案的两条边因为不需要除2了。如果能完全约分则还需要在分子的a或者b上乘一个2,哪个小乘哪个就好了。为什么乘2不会超过原来的n或者m?因为我们这时候一定是n*m%k==0,而且题中k>=2,所以n和m至少有一个可以除一个2。
感觉做的时候问题主要在于无法验证正确性,但是后来发现k>=2这个条件是极其重要的。。。。没有这个条件就可能无解了

 

#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int mod=1e9+7;

LL gcd(LL a,LL b)
{
    return !b?a:gcd(b,a%b);
}

int main()
{
    LL n,m,k;
    cin>>n>>m>>k;
    if(2*n*m%k)
        cout<<"NO\n";
    else
    {
        cout<<"YES\n";
        LL g1=gcd(n,k);
        k/=g1;
        LL g2=gcd(m,k);
        LL ng=n/g1;
        LL mg=m/g2;
        if(g2==k)
        {
            if(ng
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据