C++竞赛题解析：高效求解因数对算法

1. 题目背景与需求分析

"乘积的秘密"是上海计算机学会2026年2月月赛C++丙组的第一道题目，属于典型的数学与编程结合的入门级竞赛题。这类题目通常考察选手的基础编程能力和数学思维，适合刚接触算法竞赛的选手练习。

题目核心要求是：给定一个正整数n，找出所有满足a×b=n的正整数对(a,b)，其中a≤b，并按照a的升序输出这些数对。例如，当n=6时，符合条件的数对有(1,6)、(2,3)。

1.1 题目理解要点

1. 输入输出要求：输入是一个正整数n（通常题目会给出范围限制，比如1≤n≤10^6），输出是所有满足条件的数对，每行一个数对，格式为(a,b)。

2. 数学本质：这实际上是求一个数的所有因数对，也就是找出n的所有因数，然后配对。

3. 算法选择：最直观的方法是遍历1到n的所有整数，检查是否能整除n。但这种方法效率不高，对于大n会超时。更优的方法是遍历到√n即可。

2. 解题思路与算法设计

2.1 暴力解法及其局限性

最直接的思路是使用双重循环：

cpp复制for(int a=1; a<=n; a++){
    for(int b=a; b<=n; b++){
        if(a*b == n){
            cout << a << " " << b << endl;
        }
    }
}

这种方法的时间复杂度是O(n²)，当n较大时（比如n=10^6），循环次数将达到10^12次，显然无法在竞赛时间限制内完成。

2.2 优化思路：单层循环与数学性质

观察到如果a是n的因数，那么必然存在一个b=n/a，使得a×b=n。因此，我们只需要找到所有满足a≤b的因数a即可，这可以通过单层循环实现：

1. 遍历a从1到√n
2. 如果n能被a整除，则(a, n/a)就是一个有效的数对
3. 需要特别处理a×a=n的情况，避免重复输出

这种算法的时间复杂度降为O(√n)，对于n=10^6，最多只需循环1000次，效率大幅提升。

2.3 边界条件与特殊处理

在实际编码中需要考虑以下特殊情况：

• n=1时，输出只有(1,1)
• 完全平方数（如n=16）时，(4,4)只需输出一次
• 题目是否保证n为正整数（通常竞赛题会明确说明