Codeforces Round #512(Technocup 2019 Elimination Round 1) D. Vasya and Triangle (Codeforces 1030D)

xiaoxiao2021-03-01  15

题目: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; }
转载请注明原文地址: https://www.6miu.com/read-4050109.html

最新回复(0)