Codeforces Round #761 (Div. 2) B. GCD Problem
2022/9/14 23:17:13
本文主要是介绍Codeforces Round #761 (Div. 2) B. GCD Problem,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
B. GCD Problem
题目Link
题意
\(T (1 \le T \le 100000)\) 组数据,给定一个数字 \(n (10 \le n \le 10^9)\),请你找出三个不同的正整数 \(a, b, c\) 满足 \(a + b + c = n\),并且 \(gcd(a, b) = c\)。
SOLUTION
思路一:
首先想到对 \(n\) 分解质因数,然后枚举 \(c\),但是这样复杂度是不太对的。 考虑固定 \(c = 1\),然后题目转化为枚举 \(a, b\),即将 \(n - 1\) 分成两个互质的数字的和\((a,b \ge 2)\),由于 \(n-1\)不可能是很多质数的倍数,因此暴力枚举 \(a,b\) 即可。
代码一:
点击查看代码
inline void solve() { int n; read(n); for(int i = 2; ; i ++ ) if(gcd(i, n - i - 1) == 1) { printf("%d %d %d\n", i, n - i - 1, 1); break; } }
思路二
分析和思路一一样,但是我们可以随机化!
代码二
点击查看代码
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); void solve() { int n; cin >> n; while (true) { // 生成 (2 - n - 2) 的随机数 int a = rnd() % (n - 3) + 2; // int a = uniform_int_distribution<int>(2, n - 2)(rnd); int b = n - a - 1; if (a != 1 && b != 1 && __gcd(a, b) == 1) { cout << a << " " << b << " " << 1 << "\n"; break; } } }
这篇关于Codeforces Round #761 (Div. 2) B. GCD Problem的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享