B. Crimson Triples（Codeforces 2238）-北京尧图网络

B. Crimson Triples - 题解题意简述给定n要统计有多少个有序三元组(a, b, c)满足1 a, b, c n并且gcd(lcm(a, b), lcm(b, c)) gcd(a, c)注意三元组是有序的(1, 2, 3)和(3, 2, 1)算不同。核心结论一个三元组(a, b, c)满足条件当且仅当b | a 且 b | c也就是b同时整除a和c。接下来解释为什么。从质因数指数理解任意正整数都可以拆成质因数。我们只看某一个质因子p。设p在a, b, c中出现的次数分别为x v_p(a) y v_p(b) z v_p(c)例如a 12 2^2 * 3^1 v_2(12) 2 v_3(12) 1对于质因数指数有两个基本规则v_p(gcd(u, v)) min(v_p(u), v_p(v)) v_p(lcm(u, v)) max(v_p(u), v_p(v))所以原式左边在质因子p上的指数是v_p(gcd(lcm(a, b), lcm(b, c))) min(max(x, y), max(y, z))右边在质因子p上的指数是v_p(gcd(a, c)) min(x, z)因此要求min(max(x, y), max(y, z)) min(x, z)化简这个条件观察左边max(x, y) y max(y, z) y所以min(max(x, y), max(y, z)) y如果y min(x, z)那么左边至少是y会严格大于右边条件不成立。如果y min(x, z)说明y x 且 y z于是max(x, y) x max(y, z) z左边变成min(x, z)正好等于右边。所以对于每一个质因子都必须且只需满足y x 且 y z翻译回整数就是b | a 且 b | c计数方法固定中间的数b。由于必须满足b | a b | c所以a和c都必须是b的倍数。在1..n中b的倍数有floor(n / b)个b, 2b, 3b, ..., floor(n / b) * ba可以任选一个倍数c也可以任选一个倍数所以固定b时贡献为floor(n / b) * floor(n / b)把所有b 1..n的贡献加起来answer sum_{b1}^{n} floor(n / b)^2图表示意以n 6为例固定的b1..6中b的倍数可选数量mfloor(n/b)贡献m^211, 2, 3, 4, 5, 663622, 4, 63933, 624441155116611总答案36 9 4 1 1 1 52也可以这样理解固定 b a 的选择b, 2b, 3b, ... c 的选择b, 2b, 3b, ... 每一个 a 都可以和每一个 c 配对所以是一个 m * m 的方阵。算法流程对每个测试用例读入n初始化ans 0枚举b从1到n令m n / b累加ans m * m输出ans。易错点三元组是有序的a和c不能合并计数。不是统计gcd(a, c)的值而是统计所有满足条件的(a, b, c)。答案可能很大必须使用long long。例如n 200000时光是b 1的贡献就是200000^2 40000000000。题目保证所有测试用例的n之和不超过2 * 10^5所以每个测试用例直接O(n)枚举是足够的。复杂度分析设所有测试用例的n之和为S。时间复杂度O(S) 空间复杂度O(1)其中题目保证S 2 * 10^5。C 代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){longlongn;cinn;longlongans0;// 固定中间的 b。// 条件等价于 b | a 且 b | c。// 在 1..n 中b 的倍数有 floor(n / b) 个。for(longlongb1;bn;b){longlongmultiplesn/b;ansmultiples*multiples;}coutans\n;}return0;}

B. Crimson Triples（Codeforces 2238）

相关推荐

为什么STARsolo是单细胞RNA测序分析的终极加速器？

Si5351A时钟发生器与PIC18F4680的精准时钟系统设计

如何在5分钟内免费永久激活Windows和Office：KMS智能激活完整指南

更多资讯

Docker容器GPU加速实战：CUDA驱动与框架版本对齐指南

10个提升Mac Dock效率的实用技巧

Git删除指定commit的完整操作指南

AI Agent开发中Skills的演进与实战应用

Git删除特定commit的实用指南与最佳实践

Agent-Reach：面向AI Agent的轻量级跨平台API通信中枢

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？