第十五届蓝桥杯c++B组：宝石组合

蓝桥杯真题宝石组合#includebits/stdc.h // 万能头文件包含了C所有标准库 using namespace std; // 自定义函数求三个数的最小公倍数LCM int LCM(int x, int y, int z) { int maxx max(x, max(y, z)); // 找出 x,y,z 中的最大值作为循环的起始点 int sum x * y * z; // 三个数的乘积作为循环的终点因为乘积一定是公倍数 // 从最大值开始逐个检查找到第一个能同时被 x,y,z 整除的数即最小公倍数 for (int i maxx; i sum; i) { if (i % x 0 i % y 0 i % z 0) { return i; // 找到后立即返回这个最小公倍数 } } return sum; // 理论上不会执行到这里但防止编译器警告返回乘积 } int main() { int N, result, maxxx 0; // N:数字个数, result:临时存储计算结果, maxxx:记录最大结果值 cin N; // 输入数字个数 int s[N]; int ans[3] {0}; // 存储最终结果的三个数初始化为0 // 循环读入N个数字 for (int i 0; i N; i) { cin s[i]; // 将输入的数字存入数组 } sort(s, s N); // 对数组进行升序排序方便后续按字典序选择 // 三重循环枚举所有可能的三元组 (a, b, c) for (int a 0; a N; a) { // 第一个数的索引 for (int b a 1; b N; b) { // 第二个数的索引必须大于a保证不重复且有序 for (int c b 1; c N; c) { // 第三个数的索引必须大于b // 核心公式计算当前三元组的魅力值或美丽度 // 公式来源蓝桥杯宝石组合问题 // 写成这样是为了避免整数除法提前截断导致结果为0 result (s[a] * s[b] * s[c] * LCM(s[a], s[b], s[c])) / (LCM(s[a], s[b], 1) * LCM(s[a], s[c], 1) * LCM(s[b], s[c], 1)); // 如果当前计算结果比之前记录的最大值还要大 if (result maxxx) { maxxx result; // 更新最大值 ans[0] s[a]; // 记录当前三元组的第一个数 ans[1] s[b]; // 记录当前三元组的第二个数 ans[2] s[c]; // 记录当前三元组的第三个数 } // 注意如果result相等由于循环顺序保留的是字典序较小的那组 } } } // 输出结果三个数空格隔开 cout ans[0] ans[1] ans[2]; return 0; }result s[a] * s[b] * s[c] * ( LCM(s[a],s[b],s[c]) / (LCM(s[a],s[b],1) * LCM(s[a],s[c],1) * LCM(s[b],s[c],1)) );❌错误举例验证取 x1, y2, z4LCM(1,2,4) 4LCM(1,2,1) LCM(1,2) 2LCM(1,4,1) LCM(1,4) 4LCM(2,4,1) LCM(2,4) 4代入公式result 1*2*4 * ( 4 / (2*4*4) ) 8 * ( 4 / 32 ) 在 C 整数除法中4/32 0所以result 8 * 0 0因为我的LCM函数里包含 1。一旦三元组里包含 1很多 LCM 会变小导致分子/分母很可能小于 1整数除法得 0。怎么解决把除法放在最后一步用浮点数计算或者改成result (s[a] * s[b] * s[c] * LCM(s[a], s[b], s[c])) / (LCM(s[a], s[b], 1) * LCM(s[a], s[c], 1) * LCM(s[b], s[c], 1));这样先乘后除保证分子足够大不会过早截断成 0。