Codeforces Round #512 (Div. 2) D. Vasya and Triangle

xiaoxiao2021-03-01  25

【题目链接】

题意

给你三个数字n m k,问你能否找到一个三角形面积为n * m / k,其中保证三角形三个点均为整数,并且横坐标x满足0 < x < n,纵坐标y满足0 < y < m,如果存在该三角形,输出YES,并输出三个点的坐标,否则,直接输出NO。

examples

input 4 3 3 output YES 1 0 2 3 4 1

input 4 4 7 output NO

思路

1.每个坐标为整数的三角形的面积 * 2是整数。(可证明) 2.由1可得若存在满足题意的三角形,则n,m,k一定满足式子 2mn % k == 0。所以此时可以判掉NO的情况,剩下的一定是YES。 3.讨论三种情况 (2m) % k == 0,(2n) % k == 0,(2mn)%k == 0。 a.(2m)%k==0,横坐标可以为n,满边,纵坐标为2m/k。 b.同理,纵坐标为m,横坐标为2n/k。 c.此时可知2m%k!=0 ,2n%k!=0,2mn%k == 0。 此时没有边是满边,所以此时求t = gcd(2n,k)t!=1,并且此时横坐标为2n/t,纵坐标可以由面积 * 2 / 横坐标得到(m * t)%k。

AC代码

#include <iostream> #define ll long long using namespace std; ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a%b); } int main() { ll n, m, k; scanf("%lld%lld%lld", &n, &m, &k); ll ans = n * m * 2 % k; if (ans == 0) { printf("YES\n"); printf("0 0\n"); if ((2 * m) % k == 0) { printf("%lld 0\n", n); printf("0 %lld\n", (2 * m) / k); } else if ((2 * n) % k == 0) { printf("%lld 0\n", (2 * n) / k); printf("0 %lld\n", m); } else { ll t = gcd(2 * n, k); printf("%lld 0\n", 2 * n / t); printf("0 %lld\n", m*t / k); /* ll t = gcd(2 * m, k); printf("%lld 0\n", n*t / k); printf("0 %lld\n", 2 * m / t); */ } } else printf("NO"); }
转载请注明原文地址: https://www.6miu.com/read-4049990.html

最新回复(0)