codeforces 1030D Vasya and Triangle【思维+gcd】
2024-08-27 14:44:38
题目:戳这里
题意:选出三个点构成三角形,要求面积为n*m/k。
解题思路:因为三个点的坐标都是正整数,根据三角形面积公式(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2=n*m/k可知,若三角形存在,则2*n*m/k必为整数。若面积*2为整数,则把该三角形放置在x轴上即可。于是设x1=0,y1=0,x2=a,y2=0,x3=0,y3=b;求a*b=2*n*m/k。(0<=a<=n,0<=b<=m)
欲找到满足条件,可以利用最大公约数。若gcd(2*n,k)==1,则gcd(2*m,k)>=2; b=2*m/gcd(2*m,k) <=m,a=n/(k/gcd(2*m,k)<=n,反之若gcd(2*n,k)>=2同理。
附ac代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int inf = 0x3f3f3f3f;
5 const int maxn = 2e3 + 10;
6 #define lowbit(x) x&-x
7 ll gcd(ll a, ll b) {
8 return b?gcd(b,a%b):a;
9 }
10 int main() {
11 ll n, m, k;
12 scanf("%lld %lld %lld", &n, &m, &k);
13 if(2ll * n * m %k != 0) {
14 puts("NO");
15 return 0;
16 }
17 puts("YES");
18 puts("0 0");
19 ll x2, y2, x3, y3;
20 ll sum = 2ll * n * m / k;
21 // printf("%lld\n", gcd(2ll*n,k));
22 if(gcd(2ll*n,k) == 1) {
23 ll u = gcd(2ll*m, k);
24 printf("%lld %lld\n%lld %lld", n/(k/u), 0ll, 0ll, 2ll*m/u);
25 } else {
26 ll u = gcd(2ll*n, k);
27 printf("%lld %lld\n%lld %lld", 2ll*n/u, 0ll, 0ll, m/(k/u));
28 }
29 return 0;
30 }
最新文章
- [译]DbContext API中使用SqlQuery和ExecuteSqlCommand获取存储过程的输入输出参数
- Bootstrap之样式风格与下拉菜单
- 对文本行进行排序,新增-d(目录排序),只对字母数字空格排序(TCPL 练习5-16)
- Android Fragment add/replace以及backstack
- Swift 自动布局框架-SnapKit
- MFC字体与文本输出
- Mysql数据库乱码与编码问题筛查
- 如何安装VM Tool软件包
- [Linux] PHP程序员玩转Linux系列-备份还原MySQL
- iOS 实现后台 播放音乐声音 AVAudioPlayer 以及铃声设置(循环播放震动)
- Java基础:Java虚拟机(JVM)
- JAVA EE 第二周(XML简述以及web请求的过程)
- CSS 小结笔记之em
- Jsonp的实现
- 【Nodejs】cheerio简单示例
- $.when()方法监控ajax请求获取到的数据与普通ajax请求回调获取到的数据的不同
- 【ABP】Abp的AspNetZero5.0版本无法使用ctrl+f5调式
- try catch finally 中 returne的执行顺序
- PAT 1071 Speech Patterns[一般]
- java从键盘输入一组数据,输出其最大值,平均值,最小值没法输出
热门文章
- ORACLE查找占用临时表空间多的SESSION
- yum配置文件下使用自定义变量
- Sentry(v20.12.1) K8S 云原生架构探索,JavaScript 性能监控之采样 Transactions
- 卷积神经网络学习笔记——SENet
- MYSQL基础知识的复习2
- tornado大全(甩锅版)
- vue的nuxt框架中使用vue-video-player
- Cannot assign requested address问题总结
- Linux下unix socket 读写 抓包
- 翻页bug 在接口文档中应规范参数的取值区间 接口规范