NOI真题解析：从反正切函数到整数分解的算法优化

1. 项目概述从一道NOI真题看数学与算法的精妙结合最近在带学生刷信息学奥赛信奥的历年真题又翻到了这道经典的[NOI2001]反正切函数的应用。题目本身只有短短几行描述和一个输入输出样例但第一次接触的选手很容易被其中的数学公式绕晕觉得无从下手。实际上这道题完美诠释了信奥题目的典型风格披着复杂数学外衣内核却是一个精巧的算法设计问题。它不要求你真正去计算反正切函数值而是考察你能否将数学等式转化为可编程求解的数学模型并找到高效的枚举或数学优化方法。对于正在学习C和算法竞赛的选手来说吃透这道题对理解“数学建模”和“时间复杂度优化”有极大的好处。今天我就结合自己多年的刷题和教学经验把这道题的解题思路、核心推导、多种解法实现以及避坑指南一次性讲透。2. 题目核心需求与数学建模解析2.1 问题重述与初步理解题目给出的核心等式是arctan(1/a) arctan(1/b) arctan(1/c)其中a,b,c均为正整数并且1 a 60000。我们需要做的是对于每一个输入的a找到满足上述等式的正整数b和c并输出所有解中bc最小的那个值。题目保证对于任意a都存在整数解。很多新手看到arctan就发怵想着是不是要调用数学库去计算近似值然后比较。这完全走错了方向。信奥题目中一旦出现这类函数十有八九是要你利用其数学性质进行代数变换从而消去函数本身得到一个纯粹的整数关系式。2.2 关键数学推导消去反正切函数解题的钥匙就在题目正文里给出的公式(4)arctan(p) arctan(q) arctan[(pq)/(1-pq)]前提是pq 1。在我们的问题中令p 1/b,q 1/c。代入公式(4)arctan(1/b) arctan(1/c) arctan[ (1/b 1/c) / (1 - 1/(b*c)) ]等式右边合并一下(1/b 1/c) (c b) / (b*c)(1 - 1/(b*c)) (b*c - 1) / (b*c)两者相除[(bc)/(b*c)] / [(b*c-1)/(b*c)] (bc) / (b*c - 1)因此原等式arctan(1/a) arctan(1/b) arctan(1/c)可以转化为arctan(1/a) arctan[ (bc) / (b*c - 1) ]由于反正切函数arctan(x)在定义域内是单调函数我们可以直接去掉两边的arctan得到最核心的整数方程1 / a (b c) / (b * c - 1)2.3 将分式方程转化为整数方程对上式进行交叉相乘1 * (b * c - 1) a * (b c)即b * c - 1 a * b a * c这是一个关于b和c的二元二次不定方程。我们的目标是找到所有正整数解(b, c)并求min(bc)。直接求解这个方程仍然困难我们需要进一步变换将其化为更容易处理的形式。将含b和c的项移到一边b * c - a * b - a * c 1观察左边我们可以尝试配凑(b - 某个数)(c - 某个数)的形式。经过尝试发现两边同时加上a²可以完成配方b * c - a * b - a * c a² 1 a²左边可以因式分解为(b - a) * (c - a) a² 1这是本题最关键的推导步骤。至此我们成功地将一个涉及三角函数的复杂问题转化为了一个清晰的整数分解问题寻找两个正整数(b-a)和(c-a)使得它们的乘积等于a² 1。2.4 变量替换与问题最终形式令x b - ay c - a其中x和y必须是正整数因为b a,c a否则1/b或1/c将大于1/a导致等式无法成立可以简单证明。那么原方程变为x * y a² 1并且b x ac y a我们需要最小化的目标b c (x a) (y a) x y 2a。由于a是给定的常数2a是固定值。因此最小化bc等价于最小化x y。于是问题最终简化为已知正整数a令N a² 1。将N分解为两个正整数的乘积N x * y求所有分解中(x y)的最小值。3. 算法思路设计与复杂度分析3.1 暴力枚举法及其局限性最直接的想法是枚举x。因为x是N的因子所以x的取值范围是1到N。对于每一个x检查N % x 0然后计算y N / x再计算x y并记录最小值。这种方法的时间复杂度是O(N)即O(a²)。当a最大为 60000 时N ≈ 3.6 × 10⁹。枚举 36 亿个数显然是不可接受的在竞赛的时空限制下必然超时。3.2 利用因子对称性优化枚举我们知道对于N x * y当x和y越接近时x y的值越小根据基本不等式xy 2√(xy)当且仅当xy时取等号。因此为了找到xy的最小值我们应该从x最接近√N的地方开始寻找。更具体地说我们只需要枚举x从1到√N即sqrt(a²1)。对于每一个能整除N的x计算y N / x那么(x, y)和(y, x)是同一对因子的两种对称表示。由于我们要最小化xy而xy的值对于(x, y)和(y, x)是相同的所以我们只需要考虑x y的情况即x从1枚举到√N。这样时间复杂度降为O(√N)即O(a)。对于a60000√N ≈ 60000枚举6万次在3秒的时限内是绰绰有余的。3.3 算法步骤梳理输入读取正整数a。计算N a * a 1。注意数据范围a²最大为3.6e9在 C 的int范围内约2.1e9会溢出。因此必须使用long long类型。初始化设置min_sum为一个很大的数如LLONG_MAX用于记录最小的xy。枚举循环x从1到sqrt(N)包含。如果N % x 0说明x是N的一个因子。计算y N / x。计算当前的和current_sum x y。如果current_sum min_sum则更新min_sum。输出最终的答案ans min_sum 2 * a。注意这里有一个极其关键的边界条件。我们之前假设x和y是正整数即b a且c a。这要求x 1且y 1这自然满足。但是我们还需要确保b和c是正整数这由x, y, a均为正整数保证。此外还需要验证b和c是否满足原始的反正切公式理论上由数学推导的每一步都是等价变换在pq1即1/(b*c) 1的条件下这显然成立所以只要x和y是正整数得到的b,c就是合法解。题目也保证了解的存在性。4. C代码实现与逐行详解接下来我们给出完整的C代码并详细解释每一部分的意图和注意事项。#include iostream #include cmath #include climits using namespace std; int main() { // 使用 long long 防止平方运算溢出 long long a; cin a; // 计算 N a^2 1 long long N a * a 1; // 初始化最小和为最大值 long long min_xy_sum LLONG_MAX; // 枚举因子 x从 1 到 sqrt(N) // 使用 long long 类型循环变量因为 N 很大 long long sqrtN (long long)sqrt(N); for (long long x 1; x sqrtN; x) { // 如果 x 是 N 的因子 if (N % x 0) { long long y N / x; // 对应的另一个因子 long long current_sum x y; // 更新最小和 if (current_sum min_xy_sum) { min_xy_sum current_sum; } } } // 最终答案b c (x y) 2a long long ans min_xy_sum 2 * a; cout ans endl; return 0; }代码关键点解析数据类型选择 (long long)这是本题第一个坑。a最大为 60000a²等于 36亿已经超过了 32位int型变量的最大值约21亿。如果使用int存储N会发生溢出导致计算错误。因此所有与a,N,x,y相关的变量都必须使用long long64位整数。平方根的计算与转换sqrt()函数参数和返回值都是double类型。为了在循环中使用我们将其强制转换为long long并赋值给sqrtN。这里直接取整是安全的因为如果sqrt(N)不是整数那么循环到其整数部分即可不会漏解因为因子是成对出现的大于sqrt(N)的因子y必然对应一个小于sqrt(N)的因子x。循环边界x sqrtN这里必须是。考虑N是完全平方数的情况例如a1时N2不是完全平方数。但如果N是完全平方数比如N36那么sqrtN6因子对(6,6)的x正好等于sqrtN必须被枚举到。使用可以确保包含这种情况。更新最小值初始化min_xy_sum为LLONG_MAX在climits中定义这是long long可表示的最大值确保第一次比较一定能更新。答案计算最终输出min_xy_sum 2 * a不要忘记加上2a。4.1 测试与验证我们用手动计算和样例来验证一下。样例输入1a 1,N 1*1 1 2。sqrt(N) ≈ 1.414取整后sqrtN 1。枚举x从1到1x1N % 1 0成立。y 2 / 1 2。current_sum 1 2 3。min_xy_sum 3。ans 3 2*1 5。 输出5与样例一致。我们再测试一个稍大的数比如a 10。N 10*10 1 101。sqrt(101) ≈ 10.05sqrtN 10。枚举x从1到10寻找101的因子。发现101是质数只有因子1和101。x1,y101,sum102。ans 102 2*10 122。 我们可以心算验证b 11011,c10110111,bc122。或者b111,c11和相同。这看起来是唯一解。5. 算法优化与数学深入探讨5.1 枚举的进一步优化上面的算法复杂度是O(a)对于a60000已经足够快。但我们可以思考是否还有优化的空间我们的目标是找到N a²1的因子对(x, y)使得xy最小。由于x和y是正整数且x * y N为定值根据均值不等式当x和y越接近时xy越小。因此使得xy最小的因子对就是N的所有因子对中两个因子大小最接近的那一对。换句话说x是小于等于√N的最大的那个N的因子。那么我们不需要枚举所有1~√N的数只需要从√N向下枚举找到的第一个能整除N的x就是我们要找的此时y N / x它们的和就是最小的。优化后的循环部分long long x; for (x sqrtN; x 1; --x) { if (N % x 0) { break; // 找到就立刻跳出 } } // 如果找到了题目保证有解所以一定能找到 long long y N / x; long long ans (x y) 2 * a;这样最坏情况下当N是质数时依然需要枚举大约√N次但平均情况会快很多因为大的数更可能是质数循环很快就会在靠近√N的地方找到因子1等等这里有个逻辑问题。仔细想一下如果N是质数它的因子只有1和N。小于等于√N的最大的因子就是1。从√N向下枚举会一直枚举到x1才找到。这和正向枚举的步数是一样的。所以这个优化在最坏情况下并没有降低时间复杂度仍然是O(√N)。但它有一个好处一旦N有一个较大的接近√N的因子它能很快找到从而在平均情况下表现更好。不过对于本题a的范围原始的O(a)算法已经足够这种优化属于锦上添花。5.2 关于解的存在性与唯一性题目保证对于任意a都存在整数解。从我们的模型x*y a²1来看a²1至少可以分解为1 * (a²1)这对应x1, ya²1从而得到ba1, ca²a1。这确实是一组正整数解。所以解总是存在的。关于bc的最小解是否唯一不一定。例如当N有多组因子对时xy的值可能相同吗有可能比如N12因子对有(2,6)和(3,4)它们的和分别是8和7不同。但N16因子对有(2,8)和(4,4)和分别是10和8。当N为完全平方数时xy√N的和2√N是最小的。对于其他因子对由于偏离相等程度更大和也会更大。所以最小和通常对应最接近的那对因子。如果N有两对因子与√N的距离完全相同那么它们会产生相同的xy。但根据我们的枚举方法找第一个x √N的因子我们找到的是满足x √N的最大的x这正好对应了x和y最接近的情况。如果存在多组解和相同我们找到的这组解是有效的解之一符合题目要求输出bc最小的解如果多个解bc相同任选一个输出即可。6. 常见错误与调试技巧实录在实现和调试这道题时选手们常会遇到以下几个问题6.1 整数溢出问题这是最高频的错误。错误代码int a; cin a; int N a * a 1;后果当a 46340约时a*a超过int最大值发生溢出N变成负数或错误的值导致后续计算全部错误。解决方法统一使用long long。long long a; cin a; long long N a * a 1;6.2 循环变量类型错误错误代码for (int x 1; x sqrt(N); x)后果sqrt(N)是double与int比较可能存在精度问题。更重要的是如果N很大接近10^10sqrt(N)约10^5循环次数很多但int类型的x在累加时不会溢出。然而在判断N % x时x是intN是long longC会进行隐式类型转换通常没问题但为了安全性和一致性建议循环变量也使用long long。正确写法long long sqrtN (long long)sqrt(N); for (long long x 1; x sqrtN; x)6.3 忽略边界条件x sqrtN错误代码for (long long x 1; x sqrtN; x)用了而不是后果当N为完全平方数时会漏掉x sqrtN这个因子从而可能找不到和最小的因子对因为xy时和最小。例如虽然本题中a²1几乎不可能是完全平方数除了a0但题目a1但作为一种良好的编程习惯和通用性考虑应该使用。解决方法牢记循环边界应包含等于的情况。6.4 对数学推导的理解不透彻有同学可能会问为什么令x b-a,y c-a为什么x和y一定是正整数解释从原始方程b*c - 1 a*b a*c到(b-a)(c-a)a²1的配凑是解题的精髓。需要一定的数学观察力。多做一些类似的因式分解题目可以培养这种能力。关于正整数的证明假设b a那么1/b 1/a。由于c是正整数1/c 0所以arctan(1/b) arctan(1/c) arctan(1/a)这与等式矛盾。因此必有b a同理c a。所以x b-a 0,y c-a 0。6.5 调试技巧如果程序提交后 Wrong AnswerWA可以尝试以下方法小数据验证编写一个暴力验证程序对于小的a比如a100用双重循环枚举所有可能的b和c范围可以设得大一些比如到10000直接计算arctan(1/a)和arctan(1/b)arctan(1/c)的近似值使用atan函数double类型如果两者差的绝对值很小如1e-10则记录bc。然后与你的优化算法的结果对比。这可以确保你的数学推导和算法逻辑在较小范围内是正确的。中等数据测试选取几个中等大小的a如1000, 5000手动或通过暴力程序可能较慢计算出答案与你的程序输出对比。大数据边界测试测试a60000确保程序不会超时或溢出。计算出的结果应该是一个很大的数检查其合理性例如b和c应该都远大于a。输出中间变量在本地调试时可以输出N,sqrtN, 以及找到的x,y看看是否符合预期。7. 总结与举一反三这道[NOI2001]反正切函数的应用是一道质量极高的题目。它从一个复杂的数学公式出发通过一步步严谨的代数推导最终归结到一个简洁的数论问题——求一个数的因子中和最接近的那一对。这个过程涵盖了数学建模、公式推导、算法优化等多个核心竞赛技能点。解决这类题目的通用思路是耐心读题提取关键信息不要被表面吓倒仔细阅读题目给出的每一个公式和提示。尝试消去复杂函数利用函数性质如单调性、和差公式进行代数变换将问题转化为纯代数或数论问题。简化方程寻找规律对得到的方程进行因式分解、变量代换将其化为更易于处理的形式。分析数据范围设计算法根据最终模型如x*yN和输入范围a≤60000设计出满足时空限制的算法如O(√N)的枚举。注意细节谨慎编码特别注意数据类型的选取防溢出、循环边界的处理、特殊情况的考虑。这道题还可以引申出一些相关的思考题如果题目要求输出具体的b和c而不仅仅是bc代码该如何修改找到x和y后输出bxa,cya即可如果a的范围扩大到10^12甚至更大O(√N)的算法也会超时有没有更快的算法这涉及到对大整数Na²1进行质因数分解然后通过因子组合来寻找和最接近的因子对难度会大大增加希望通过这道题的详细拆解你能掌握将数学问题转化为算法问题的核心方法。在信奥之路上这种能力远比死记硬背算法模板重要得多。多练习这类题目你的思维能力和解题水平一定会得到质的提升。