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

时间:2021-12-14 08:10:29

参考了别人的思路:https://blog.csdn.net/qq_41608020/article/details/82827632

         http://www.cnblogs.com/qywhy/p/9695344.html

首先根据皮克定理,2*m*n/k一定要是一个整数,也就是说2*m*n%k !=0 的都可以不用算了

最简单的构造方法肯定是 (a,0),(0,b)

2*n*m%k ==0,把2*n*m看成2*n和m两部分,k中的质因子,一部分在2*n中,一部分在m中,当然这个“一部分”可以是0

例子:2*3*5%15 == 0   k的质因子分别来自n和m

当k和2*n含有相同的质因子时

令t=gcd(2*n,k)   t一定大于等于2

令a = 2n/t     a一定小于n

b = (2*m*n)/(a*k)

b=m*t/k     b一定小于等于m(因为t一定大于等于k)

当k和2*n不含相同质因子时

那么质因子就全部包含在m里面

直接令a = n   b = 2*m/k 即可   因为k >= 2  所以不会超范围

ac:代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long n,m,k;
ll gcd(ll a,ll b)
{
if (b==0) return a;
return gcd(b,a%b);
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
if (n*m*2%k!=0)
{
printf("NO");
return 0;
}
printf("YES\n0 0\n");
long long g = gcd(2*n,k);
if(g == 1)
{
ll a = n;
ll b = 2*m/k;
printf("%lld 0\n",a);
printf("0 %lld\n",b);
}
else
{
ll a = 2*n/g;
ll b = m*g/k;
printf("%lld 0\n",a);
printf("0 %lld\n",b);
}
}

  

Codeforces Round #512 (Div. 2) D. Vasya and Triangle的更多相关文章

  1. Codeforces Round &num;512 &lpar;Div&period; 2&rpar; D&period;Vasya and Triangle 数学

    题面 题意:给你n,m,k,在你在(0,0)到(n,m)的矩形内,选3个格点(x,y都是整数),使得三角形面积为n*m/k,不能找到则输出-1 题解:由毕克定理知道,格点多边形的面积必为1/2的整数倍 ...

  2. Codeforces Round &num;512 &lpar;Div&period; 2&rpar; D&period; Vasya and Triangle(几何&plus;思维)

    题目 题意: 给出 n,m,k ,让你在长为 n,宽为 m 的坐标系里构建一个三角形,使得面积= n*m/k.如果存在,输出“YES”,输出三角形三个顶点的坐标:  如果不存在,输出“NO”. 思路: ...

  3. 构造水题 Codeforces Round &num;206 &lpar;Div&period; 2&rpar; A&period; Vasya and Digital Root

    题目传送门 /* 构造水题:对于0的多个位数的NO,对于位数太大的在后面补0,在9×k的范围内的平均的原则 */ #include <cstdio> #include <algori ...

  4. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; C&period; Vasya and Golden Ticket 【。。。】

    任意门:http://codeforces.com/contest/1058/problem/C C. Vasya and Golden Ticket time limit per test 1 se ...

  5. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; E&period; Vasya and Good Sequences(DP)

    题目链接:http://codeforces.com/contest/1058/problem/E 题意:给出 n 个数,对于一个选定的区间,区间内的数可以通过重新排列二进制数的位置得到一个新的数,问 ...

  6. Codeforces Round &num;512 &lpar;Div&period; 2&comma; based on Technocup 2019 Elimination Round 1&rpar; E&period; Vasya and Good Sequences

    题目链接 官网题解写的好清楚,和昨晚Aguin说的一模一样…… 这题只和每个数1的个数有关,设每个数1的个数的数组为$b$,就是首先一段如果是好的,要满足两个条件: 1.这一段$b$数组和为偶数,因为 ...

  7. Codeforces Round &num;322 &lpar;Div&period; 2&rpar; A&period; Vasya the Hipster 水题

    A. Vasya the Hipster Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/581/p ...

  8. Codeforces Codeforces Round &num;319 &lpar;Div&period; 2&rpar; C&period; Vasya and Petya&&num;39&semi;s Game 数学

    C. Vasya and Petya's Game Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/ ...

  9. Codeforces Round &num;281 &lpar;Div&period; 2&rpar; B&period; Vasya and Wrestling 水题

    B. Vasya and Wrestling 题目连接: http://codeforces.com/contest/493/problem/B Description Vasya has becom ...

随机推荐

  1. less 里面 opacity的写法

    今天写了个opacity, 竟然less编译不过,上网搜了一个写法 .opacity (@opacity) { @opacityPercentage: @opacity * 100; opacity: ...

  2. git 教程(5)--工作区和暂存区

    Git和其他版本控制系统如SVN的一个不同之处就是有暂存区的概念. 工作区(working directory) 就是你在电脑里能看到的目录,比如我的learngit文件夹就是一个工作区: 版本库 ( ...

  3. kernel 模块与简单 hello 模块

    Kernel 模块与简单 hello 模块 kernel 模块的简介 Linux 内核进行扩展时,例如编写驱动程序.netfilter功能等,最方便的方式是通过编写模块,然后加载到内核中.由于 ker ...

  4. C&plus;&plus; Language

    C++ Language Reference https://msdn.microsoft.com/en-us/library/3bstk3k5(v=vs.120).aspx

  5. JAX-WS 学习二:基于WEB容器,发布WebService

    WebService 的发布通过调用 Endpoint.publish() 方法来启动一个java内嵌的WEB容器来实现的,如果要将WebService部署到一个WEB容器中去,需要使用jax-ws提 ...

  6. &period;NET&comma;你忘记了么?(八)—— 从dynamic到特性误用 &lbrack;转&rsqb;

    1. 摘要 每个程序员都想写出漂亮的代码,但是什么是漂亮,这个我想每个人都有着自己的看法.那么我就说几种典型的想法: A. 写出别人看不懂的代码,让别人觉得很高深. B. 写出简短的代码 C. 用最新 ...

  7. Ubuntu下安装Android SDK&lpar;图文教程&rpar;

    刚接触Ubuntu,对于我来说现在最迫切的就是需要把Android环境搭起来 之前我的博文中已经详细地写了JDK,Eclipse,ADT的安装..现在写下SDK的安装 1.下载Linux版本的Andr ...

  8. ThreadLocal终极源码剖析-一篇足矣!

    本文较深入的分析了ThreadLocal和InheritableThreadLocal,从4个方向去分析:源码注释.源码剖析.功能测试.应用场景. 一.ThreadLocal 我们使用ThreadLo ...

  9. 你真的了解String的常见API吗?

    面试官Q1:请问String常见的方法有哪些,列举几个? String是我们开发中使用频率最高的类,它有哪些方法,大家一定不会陌生,例如: length();//计算字符串的长度 charAt();/ ...

  10. Starting with neural network in matlab&lbrack;zz&rsqb;

    转自:http://matlabbyexamples.blogspot.com/2011/03/starting-with-neural-network-in-matlab.html The neur ...