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;}