CF1030D Vasya and Triangle
2021/6/1 10:25:23
本文主要是介绍CF1030D Vasya and Triangle,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
- 题意:在 \(1 \leqslant n \leqslant 1e9, 1\leqslant m \leqslant 1e9, 1 < k \leqslant 1e9\) 的情况下,构造出 \(1\leqslant x \leqslant n, 1 \leqslant y\leqslant m\) 同时三个点构成的三角形面积等于 \(\frac{n\times m}{k}\)。
- 题解:主要是当在抽象成 \(x\times y = \frac{n\times m}{2\times k}\) 的时候,只注意了枚举终点,但是最关键的是起点也可以,因为这是有两个限制,就是 \(x\) 和 \(y\) 都得同时满足条件,所以当 \(x\) 从 \(1\) 开始会令 \(y\) 不满足,遍历过多。
- 代码:
#include <bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll n, m, k; ll N; bool check(ll x, ll y) { if (x > N || y > m)return 0; return 1; } void solve() { scanf("%lld%lld%lld", &n, &m, &k); N = n; n = 2 * n * m; if (n % k != 0) { cout << "NO\n"; return; } n /= k; for (ll x = max(1ll, n/(max(N,m))); x * x <= n; x ++) { ll y = n/(x); if (n % x == 0 ) { if (!check(x, y)) { swap(x, y); if (check(x, y)) { cout << "YES\n"; cout << "0 0\n"; cout << 0 << " " << y << endl; cout << x << " " << 0 << endl; return; } else swap(x, y); } else { cout << "YES\n"; cout << "0 0\n"; cout << 0 << " " << y << endl; cout << x << " " << 0 << endl; return; } } } cout << "NO\n"; } int main() { #ifndef ONLINE_JUDGE freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); #endif ll n = 1; while (n--) { solve(); } return 0; }
这篇关于CF1030D Vasya and Triangle的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain