1. 项目概述从一道蓝桥杯真题看算法竞赛的实战思维最近在带学生备赛又翻到了蓝桥杯2025年国赛B组的一道题——P12836 “翻倍”。这道题乍一看描述简单就是给定两个整数A和B每次操作可以让其中一个数翻倍问最少多少次操作能让两个数相等。很多刚接触信奥或者算法竞赛的同学第一反应可能就是暴力模拟或者简单贪心但如果你真这么做了大概率会掉进坑里或者只能过部分样例。这道题真正考察的远不止是编程语法而是对数论基础、问题转化能力以及边界情况处理的综合考量。今天我就结合这道题和大家深入聊聊在信奥信息学奥林匹克和蓝桥杯这类竞赛中如何拆解一个看似简单的问题并最终用C实现一个高效且鲁棒的解法。这不仅仅是解一道题更是一次完整的算法思维训练。信奥和蓝桥杯的题目尤其是国赛级别的很少会考你直白的语法。它们更像是一个个包装好的谜题需要你剥开“操作描述”的外衣看到里面“数学本质”的内核。“翻倍”这道题就是一个典型。它适合所有正在学习C、准备参加算法竞赛或者希望提升自己问题分析和数学建模能力的同学。通过这道题你能深刻体会到为什么有些题目暴力搜索会超时而一个优秀的数学结论往往能将时间复杂度从指数级降到常数级。接下来我们就一步步拆解这道题。2. 问题本质与数学建模2.1 题目重述与初步分析题目“翻倍”的完整描述通常是给定两个正整数 A 和 B你可以进行任意次操作每次操作选择 A 或 B 中的一个将其乘以 2即翻倍。目标是使得 A 和 B 最终相等。我们需要求出达成目标所需的最少操作次数。如果无法使两者相等则输出 -1。很多新手的第一版代码会长这样用一个循环每次判断A和B谁小就给谁乘以2然后计数。直到两者相等或者某个阈值比如循环1000次后退出。这种方法对于样例A2, B3可能还能算出结果2-4, 3-6, 4-8, 6-12... 显然不对实际上2和3永远无法通过翻倍相等但对于稍大的数字或者无法达成的情况要么算错要么死循环。所以我们必须跳出“模拟操作过程”的思维定式。翻倍操作的本质是乘以2也就是在二进制表示下在数字的末尾添加一个0。那么让A和B相等实际上就是让它们二进制表示下的有效数字部分除掉末尾的零相同并且可以通过在末尾补零翻倍来调整。2.2 核心数学原理推导让我们进行更严谨的推导。设最终相等的数为X。因为操作只能翻倍所以X必须同时是 A 和 B 乘以若干个 2 后的结果。即存在非负整数k和l使得A * (2^k) XB * (2^l) X由此可得A * (2^k) B * (2^l)。我们的目标是最小化总操作次数k l。将等式变形A / B 2^(l - k)。由于A和B是整数2^(l-k)是一个2的幂。因此A除以B或B除以A的结果必须是一个2的幂包括2^01否则无解。这是本题的第一个关键判定条件。假设A B如果不满足交换即可。令ratio B / A。要使等式成立ratio必须是一个正整数并且是2的幂次即ratio 2^t其中t为非负整数。此时根据之前的等式A * 2^k B * 2^l A * ratio * 2^l可以推出2^k ratio * 2^l 2^(tl)所以k t l。我们要最小化k l t l l t 2l。由于t是固定的由输入决定要最小化总和就要最小化l。而l的最小值是多少我们需要让A和B在翻倍过程中“对齐”。更优雅的思路是不断将较大的数除以2直到两个数相等。但这里只能翻倍不能除以2。怎么办逆向思维。最终状态X是相等的从X逆向推导到 A 和 B就是不断除以2如果它是偶数。所以我们可以计算 A 和 B 不断除以2直到变成奇数为止的结果。如果这两个奇数结果不相等那么无论如何翻倍正向乘以2它们也不可能追溯到同一个奇数基底因此无解。如果这两个奇数相等记为g。那么A g * 2^aB g * 2^b。其中a和b是非负整数代表各自包含的因子2的个数。我们的操作是给A或B乘以2即增加它的a或b。目标是让a和b变得相等。假设最终我们想让它们都达到max(a, b)那么A需要额外操作max(a,b)-a次B需要额外操作max(a,b)-b次。总操作次数就是(max(a,b)-a) (max(a,b)-b) 2*max(a,b) - (ab)。但这是最优的吗不一定。我们最终相等的数X g * 2^c其中c max(a, b)。因为我们可以给较小的数a或b小的那个多翻倍几次让它们的指数都达到某个更大的c。设最终指数为c则总操作次数为(c - a) (c - b) 2c - (ab)。为了最小化这个值我们需要最小化c。同时c必须满足c a且c b。所以c的最小值就是max(a, b)。因此最小操作次数就是2 * max(a, b) - (a b)。这个结论非常简洁。它告诉我们解题步骤是将 A 和 B 不断除以2直到它们都变成奇数。比较这两个奇数是否相等。如果不相等输出 -1。如果相等统计原始 A 和 B 各自能被2整除的次数记为cntA和cntB。答案 2 * max(cntA, cntB) - (cntA cntB)。注意这里有一个非常重要的边界情况就是 A 或 B 为 0 的情况。因为0除以2永远是0会导致无限循环。竞赛题中通常规定是正整数但为了代码健壮性我们可以考虑如果 A 或 B 为 0那么只有当另一个数也为0时它们才相等操作次数为0。如果另一个数是正数由于0翻倍还是0永远无法等于一个正数所以无解。题目若明确说是正整数则可不处理。2.3 算法复杂度分析这个算法的核心是计算每个数能被2整除的次数也就是求二进制表示下末尾0的个数。这可以通过循环除2或者使用位运算(x -x)找到最低位的1然后计算位置差来实现。循环除2的次数最多为log2(A)或log2(B)因此时间复杂度是O(log(max(A, B)))对于题目可能的数据范围比如 10^9来说这几乎是瞬间完成的远远优于任何暴力或搜索算法。空间复杂度是O(1)只用了几个变量。3. C代码实现与逐行解析理解了数学原理代码实现就非常直观了。下面给出一个健壮且高效的C实现并附上详细注释。#include iostream #include algorithm // 用于 max 函数 using namespace std; // 函数计算一个数x能被2整除的次数即因子2的个数 int countFactorTwo(long long x) { int cnt 0; // 注意如果x0这个循环会无限进行。因此调用此函数前需确保x0。 while (x % 2 0) { x / 2; cnt; } return cnt; } int main() { long long A, B; cin A B; // 处理特殊情况如果两者初始就相等无需操作 if (A B) { cout 0 endl; return 0; } // 处理含0的情况根据题目数据范围调整若明确为正整数可省略 if (A 0 || B 0) { // 只有两者都为0时才相等 if (A 0 B 0) { cout 0 endl; } else { cout -1 endl; } return 0; } // 计算A和B不断除以2直到奇数的结果 long long baseA A, baseB B; while (baseA % 2 0) baseA / 2; while (baseB % 2 0) baseB / 2; // 核心判定奇数基底是否相同 if (baseA ! baseB) { cout -1 endl; return 0; } // 计算原始A和B中因子2的个数 int cntA countFactorTwo(A); int cntB countFactorTwo(B); // 套用公式计算最小操作次数 int ans 2 * max(cntA, cntB) - (cntA cntB); cout ans endl; return 0; }代码关键点解析数据类型选择使用了long long来存储 A 和 B。这是因为在计算过程中虽然输入可能是在 int 范围内但一些思路不清晰的暴力解法可能会进行乘法导致溢出。使用long long是竞赛中的好习惯可以避免许多隐蔽的错误。countFactorTwo函数这个函数封装了计算因子2个数的逻辑。虽然简单但单独写成函数提高了代码的可读性和复用性。在性能要求极高的场景可以用内联函数或者位运算优化例如__builtin_ctz在GCC/Clang中用于计算末尾零的个数但需要注意0的输入。先验相等判断在开始任何计算前先判断A B这是一个有效的剪枝也符合逻辑。基底计算while循环直接修改baseA和baseB直到它们为奇数。这里没有调用countFactorTwo是为了避免重复计算虽然对性能影响微乎其微但体现了清晰的逻辑分离先判断是否有解基底相同再计算具体操作数。公式计算ans 2 * max(cntA, cntB) - (cntA cntB)是核心。你可以验证一下例如A2 (cntA1), B8 (cntB3)max3, 公式得2*3 - (13) 2。最优操作是A翻倍2次2-4-8B不动总操作2次。位运算优化版本进阶对于追求极致性能或熟悉位运算的同学计算因子2的个数有更快的办法。#include iostream #include algorithm using namespace std; // 使用位运算计算末尾零的个数对于x0 int countTrailingZeros(long long x) { if (x 0) return 64; // 对于long long0有64个末尾零但本题x0 // GCC/Clang 内置函数直接返回末尾零的个数 return __builtin_ctzll(x); } int main() { long long A, B; cin A B; if (A B) { cout 0 endl; return 0; } if (A 0 || B 0) { cout ((A 0 B 0) ? 0 : -1) endl; return 0; } // 使用位运算获取奇数基底去掉所有末尾的0即 x countTrailingZeros(x) long long baseA A countTrailingZeros(A); long long baseB B countTrailingZeros(B); if (baseA ! baseB) { cout -1 endl; return 0; } int cntA countTrailingZeros(A); int cntB countTrailingZeros(B); cout 2 * max(cntA, cntB) - (cntA cntB) endl; return 0; }注意__builtin_ctzll是GCC和Clang编译器的内置函数在Microsoft Visual C中不可用。在竞赛环境如蓝桥杯、多数OJ通常使用GCC所以可以用。如果追求可移植性还是用循环除法更稳妥。4. 测试用例与边界情况分析再好的代码没有经过充分测试也是不可靠的。对于算法题设计全面的测试用例是必备技能。针对“翻倍”这道题我们可以从以下几个维度设计测试1. 基础功能测试输入2 4-输出1(解释4是2翻倍一次得到)输入3 6-输出-1(解释3和6的奇数基底分别是3和3但632^1332^0公式计算max(0,1)1,ans2*1-(01)1等等这里出错了3和6的基底相同都是3按照我们的算法cntA0, cntB1,ans2*1-(01)1。但真的是1次操作吗让3翻倍得6或者让6翻倍得12不对目标是让它们相等。如果让3翻倍得6此时A6, B6操作1次正确。所以输出应该是1不是-1。我之前的举例有误。3和6是可以通过一次操作相等的。)输入1 8-输出3(解释1需要翻倍3次变成8或者8需要...不对8无法通过翻倍变成1。所以是1-2-4-8共3次)输入12 18-输出-1(解释1232^2, 1892^1奇数基底3和9不同无解)2. 边界与极值测试输入1 1-输出0(相等情况)输入1000000000 1000000000-输出0(大数相等)输入1 1000000000- 需要计算。1的cnt010^9的cnt是多少10^9 2^9 * 1953125? 实际上我们要算它能被2整除的次数。快速计算10^9不断除以2。这个测试用来检查时间效率。输入1073741824 1-输出30(因为1073741824 2^3012^0 max30, ans2*30-(300)30。即1需要翻30次才能变成1073741824)输入0 0-输出0(如果题目允许0)输入0 5-输出-1(如果题目允许0)3. 思维陷阱测试输入6 9-输出-1(632, 991基底3和9不同)输入24 6-输出1(2438, 632, cntA3 (因为24/212,12/26,6/23共3次), cntB1, max3, ans2*3-(31)2。但真的是2吗最优操作6翻倍一次得12此时A24,B12然后B再翻倍一次得24总操作2次。但有没有更优让A除以2不行只能翻倍。所以是2次。验证24和6基底都是3cntA3, cntB1, ans2。正确。)通过设计这些测试用例我们不仅能验证代码正确性还能加深对问题本质的理解。例如在分析3 6这个用例时就纠正了我们之前一个直觉上的错误认知认为3和6不能通过翻倍相等。实际上只要两个数的奇数基底相同就一定有解。5. 竞赛实战技巧与常见错误在蓝桥杯、信奥等竞赛的实战中解决这类题目有几个通用的技巧和需要避开的坑技巧1先数学后编码遇到操作类题目尤其是涉及倍数、因子的不要急于写模拟代码。先在草稿纸上进行数学推导寻找规律看能否将问题转化为一个简单的公式或判定条件。像“翻倍”这道题如果直接BFS模拟操作数状态空间会爆炸每次有两种选择。数学转化后问题变得极其简单。技巧2重视边界条件零值处理尽管题目可能说正整数但思考零的情况能锻炼思维的严密性。在自家调试时可以测试一下。整数溢出这是C选手的老朋友了。在计算中间结果尤其是涉及乘法时虽然本题最优解没有乘法要习惯性使用long long。输入范围仔细阅读题目数据范围。本题A和B的范围如果很大就要用long long。技巧3善用位运算对于和2的幂次相关的问题位运算往往能提供更高效、更简洁的解法。例如判断一个数是否是2的幂x 0 (x (x - 1)) 0计算一个数末尾0的个数__builtin_ctzll(x)(GCC) 或 自己写循环while ((x 1) 0)除以2的幂次x k乘以2的幂次x k在时间紧迫的竞赛中这些技巧能节省宝贵的CPU时间。常见错误误判无解条件最容易出错的就是认为两个数必须一个是另一个的2的幂次倍才有解。实际上只要它们的“奇数部分”相同就有解。例如6(110) 3*2和12(1100) 3*4基底都是3有解。操作次数计算错误推导出公式2*max(a,b) - (ab)后要验证几个例子。不要想当然。忽略初始相等如果一开始A就等于B答案是0这是一个特例需要在代码开头处理。循环终止条件错误如果使用模拟法没有设置合理的上限对于无解的情况会导致无限循环或超时。调试建议在本地编写代码时不要只依赖题目给的样例。自己构造如第4部分所示的各种测试用例特别是小数字123和存在倍数关系的数字用纸笔演算一遍预期结果再与程序输出对比。如果使用IDE如VS Code、Dev C、Code::Blocks学会使用断点和单步调试观察变量如baseA,baseB,cntA,cntB的变化过程这对于理解算法流程和查找逻辑错误至关重要。6. 举一反三相关题型与能力拓展“翻倍”这道题本质上是关于数论和操作转化的问题。掌握它之后你可以尝试解决一系列类似的问题从而巩固这种思维模式“减半”问题给定A和B每次操作可以将一个数除以2如果是偶数问最少操作使两者相等。这几乎是本题的逆过程解法非常类似也是看奇数基底是否相同然后计算除以2的次数差。但要注意因为可以除以2所以最终相等的数可以比原始数小解法是不断将较大的数除以2直到小于等于较小的数然后比较。GCD最大公约数与操作很多操作类问题最终会归结到最大公约数上。例如有一类题是每次操作可以给一个数加上或减去另一个数问能否得到目标数这通常就考察裴蜀定理Bézout‘s identity。本题中我们虽然没用GCD但“奇数基底”的概念可以理解为“除去所有因子2后的数”这与数论中“奇偶性”和“因子分离”的思想一脉相承。二进制表示问题翻倍对应二进制右移末尾添0除以2对应二进制左移去掉末尾0。将问题放在二进制视角下常常能豁然开朗。例如判断一个数能否通过若干次翻倍变成另一个数就看大数的二进制表示是否是小数二进制表示的前缀后面补零。BFS/状态搜索问题对于操作步骤较少但数学规律不明显的情况BFS是保底的解法。例如如果操作不仅是翻倍还可能加上一个固定值那么状态空间可能依然可控可以用BFS求最短路径最少操作次数。要提升解决这类问题的能力我建议系统学习数论基础整除、质因数分解、最大公约数、最小公倍数、模运算等。这是信息学竞赛的基石之一。多练习转化思维拿到题目先问自己这个操作的本质是什么在数学上对应什么运算有没有不变量或必然变化的方向参与在线刷题在洛谷、力扣LeetCode、蓝桥云课等平台搜索“数学”、“模拟”、“贪心”标签下的题目进行专项练习。从简单题开始确保完全理解再逐步挑战难题。回到我们开头说的信奥和蓝桥杯刷题目的不只是为了做出某一道题而是通过这道题掌握一类问题的思考方法。“翻倍”这道题就像一把钥匙帮你打开了“通过数学简化操作问题”这扇门。以后再遇到类似的题目你就能更快地抓住本质写出高效优雅的代码。