数字世界的两面性：从乘积组合到最大公约数的算法之旅

在算法的宇宙中，有些问题看似简单却隐藏着深不可测的复杂度，而有些问题表面复杂却有着优雅简洁的解决方案。今天，我们将探索两个截然不同但同样迷人的数学问题：生成乘积数组的方案数和找出数组的最大公约数。这两个问题就像数学世界中的\"阴\"与\"阳\"——一个需要创造性的组合构建，另一个追求本质的共性提取。

想象一下，你是一位乐高大师，面对一盒零件（质因数），需要构建出特定形状（乘积），同时遵守严格的规则（数组长度）。或者，你是一位数学侦探，需要在数字迷宫中寻找两个极端值之间的隐藏联系。这就是我们今天要探索的算法冒险！

问题一：生成乘积数组的方案数——组合数学的交响乐

题目描述：
给你一个二维整数数组 queries ，其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个元素都是正整数的数组，且满足所有元素的乘积为 ki ，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 109 + 7 取余 。

请你返回一个整数数组 answer，满足 answer.length == queries.length ，其中 answer[i]是第 i 个查询的结果。

问题深度解析

这个看似简单的问题实际上是一座组合数学的冰山。\"给定长度n和乘积k，有多少种正整数数组满足条件？\"——这问题背后隐藏着丰富的数学结构和巧妙的计数技巧。

从数学角度看，这个问题可以转化为：将k的质因数分配到n个位置的所有可能方式。每个质因数可以独立地分配到n个位置中，这引出了经典的\"星与条\"定理（Stars and Bars theorem）的应用。

算法思维剖析

解决这个问题的算法思维过程可以分解为以下几个关键步骤：

1. 质因数分解：首先将k分解为质因数的乘积形式。例如，6 = 2¹ × 3¹

2. 质因数分配：每个质因数需要独立地分配到n个位置中。对于指数为e的质因数p，将其分配到n个位置的方法数等于将e个不可区分物体放入n个可区分容器的方案数

3. 组合计数原理：使用隔板法（Stars and Bars）计算每个质因数的分配方案数。具体公式为：C(e+n-1, n-1)

4. 乘法原理应用：各个质因数的分配方案数相乘得到总方案数

5. 特殊情况处理：注意k=1时的边界情况，以及可能存在的无法形成整数解的情况

这个问题的算法复杂度主要取决于质因数分解的效率和组合数计算的预处理。聪明的解法会使用动态规划预处理组合数，或者使用卢卡斯定理等数论技巧处理大数取模问题。
示例 1：

输入：queries = [[2,6],[5,1],[73,660]]
输出：[4,1,50734910]
解释：每个查询之间彼此独立。
[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。
[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。
[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 109 + 7 取余得到 50734910 。
示例 2 ：

输入：queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：[1,2,3,10,5]

题目程序：

#include #include #define MOD 1000000007 // 定义模数，10^9+7// 计算模逆元的函数，使用费马小定理long long mod_inverse(long long a, long long mod) { long long res = 1;  // 初始化结果为1 long long exp = mod - 2; // 指数为mod-2，因为a^(mod-2) ≡ a^(-1) mod mod while (exp) { // 当指数不为0时循环 if (exp & 1) {  // 如果当前指数位为1 res = (res * a) % mod; // 将a乘入结果，并取模 } a = (a * a) % mod; // a平方，并取模 exp >>= 1;  // 指数右移一位 } return res;  // 返回逆元}// 计算组合数C(n+e-1, e)的函数，e较小long long calculate_comb(int n, int e) { long long numerator = 1; // 初始化分子为1 // 计算分子：n * (n+1) * ... * (n+e-1) for (int i = 0; i < e; i++) { numerator = numerator * (n + i) % MOD; // 连乘并取模 } long long denominator = 1; // 初始化分母为1 // 计算分母：e的阶乘 for (int i = 1; i <= e; i++) { denominator = denominator * i % MOD; // 连乘并取模 } // 计算分母的逆元 long long inv_denom = mod_inverse(denominator, MOD); // 返回组合数：分子乘以分母的逆元再取模 return numerator * inv_denom % MOD;}// 主解决函数，处理查询数组int* solve(int** queries, int queriesSize, int* queriesColSize, int* returnSize) { int* answer = (int*)malloc(queriesSize * sizeof(int)); // 分配答案数组内存 *returnSize = queriesSize; // 设置返回数组大小 for (int i = 0; i < queriesSize; i++) { // 遍历每个查询 int n = queries[i][0]; // 获取数组长度n int k = queries[i][1]; // 获取乘积k long long res = 1; // 初始化方案数为1 int temp = k; // 临时变量保存k，用于分解 // 质因数分解：从2开始试除 for (int p = 2; p * p  0) { // 如果指数大于0 // 计算该质因数的分配方案数并乘入结果 res = res * calculate_comb(n, cnt) % MOD; } } if (temp > 1) {  // 处理剩余的质因数（大于sqrt(k)的质因数） // 计算指数1的分配方案数并乘入结果 res = res * calculate_comb(n, 1) % MOD; } answer[i] = (int)res; // 将结果存入答案数组 } return answer;  // 返回答案数组}// 示例主函数，用于测试int main() { // 示例查询数据 int query1[] = {2, 6}; int query2[] = {5, 1}; int query3[] = {73, 660}; int* queries[] = {query1, query2, query3}; int queriesSize = 3; int queriesColSize[] = {2, 2, 2}; int returnSize; // 调用解决函数 int* answer = solve(queries, queriesSize, queriesColSize, &returnSize); // 输出结果 for (int i = 0; i < returnSize; i++) { printf(\"%d \", answer[i]); } free(answer); // 释放答案数组内存 return 0;}

输出结果：

数学之美

这个问题的美妙之处在于它将数论（质因数分解）、组合数学（分配问题）和算法设计（高效计算）完美地结合在一起。每一个查询都需要快速计算组合数并对大数取模，这需要算法设计者对数论和组合数学有深刻的理解。

问题二：找出数组的最大公约数——简约中的深度

题目描述：
给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

问题本质探析

\"找出数组中最大数和最小数的最大公约数\"——这个问题表面上看极其简单，甚至让人怀疑它是否值得作为一个算法问题。然而，在这种简约性背后，隐藏着深刻的数学洞察。

这个问题的关键在于认识到：数组中任意两个数的公约数一定是整个数组公约数的因子，而最大数和最小数的最大公约数实际上反映了整个数组的\"数字共性\"。

算法思维解析

解决这个问题的算法路径相对直接：

1. 寻找极值：遍历数组找到最小值和最大值

2. 计算GCD：使用欧几里得算法计算这两个数的最大公约数

3. 返回结果：得到的GCD即为答案

欧几里得算法（辗转相除法）的精妙之处在于它基于一个简单的数学原理：gcd(a, b) = gcd(b, a mod b)。这个递归定义使得我们能够高效地计算最大公约数，即使对于很大的数字。

示例 1：

输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
示例 2：

输入：nums = [7,5,6,8,3]
输出：1
解释：
nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1
示例 3：

输入：nums = [3,3]
输出：3
解释：
nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3

题目程序：

#include  // 包含标准输入输出头文件，用于printf等函数// 计算两个整数的最大公约数（GCD）的函数// 使用欧几里得算法（辗转相除法）int gcd(int a, int b) { // 如果b为0，则a就是最大公约数 if (b == 0) { return a; } // 递归调用，参数为b和a除以b的余数 return gcd(b, a % b);}// 主函数，程序入口点int main() { // 示例测试用例1 int nums1[] = {2, 5, 6, 9, 10}; // 定义整数数组 int size1 = sizeof(nums1) / sizeof(nums1[0]); // 计算数组长度 int min = nums1[0]; // 初始化最小值为数组第一个元素 int max = nums1[0]; // 初始化最大值为数组第一个元素 // 遍历数组，寻找最小值和最大值 for (int i = 1; i < size1; i++) { if (nums1[i]  max) { // 如果当前元素大于最大值 max = nums1[i]; // 更新最大值 } } // 计算最小值和最大值的最大公约数 int result1 = gcd(min, max); // 输出结果 printf(\"示例1输出: %d\\n\", result1); // 示例测试用例2 int nums2[] = {7, 5, 6, 8, 3}; // 定义第二个测试数组 int size2 = sizeof(nums2) / sizeof(nums2[0]); // 计算数组长度 min = nums2[0]; // 重置最小值为新数组的第一个元素 max = nums2[0]; // 重置最大值为新数组的第一个元素 // 遍历第二个数组，寻找最小值和最大值 for (int i = 1; i < size2; i++) { if (nums2[i]  max) { // 如果当前元素大于最大值 max = nums2[i]; // 更新最大值 } } // 计算最小值和最大值的最大公约数 int result2 = gcd(min, max); // 输出结果 printf(\"示例2输出: %d\\n\", result2); // 示例测试用例3 int nums3[] = {3, 3}; // 定义第三个测试数组 int size3 = sizeof(nums3) / sizeof(nums3[0]); // 计算数组长度 min = nums3[0]; // 重置最小值为新数组的第一个元素 max = nums3[0]; // 重置最大值为新数组的第一个元素 // 遍历第三个数组，寻找最小值和最大值 for (int i = 1; i < size3; i++) { if (nums3[i]  max) { // 如果当前元素大于最大值 max = nums3[i]; // 更新最大值 } } // 计算最小值和最大值的最大公约数 int result3 = gcd(min, max); // 输出结果 printf(\"示例3输出: %d\\n\", result3); return 0; // 程序正常退出}

输出结果：

算法效率分析

该算法的时间复杂度为：

• 寻找极值：O(n)，需要遍历整个数组

• 计算GCD：O(log(min(a,b)))，其中a和b是输入的两个数

总体复杂度为线性时间，非常高效。这种效率来自于欧几里得算法的数学美——它每次迭代都能将问题规模大致减半。

二者对比分析：算法思维的两种范式

特性维度 生成乘积数组的方案数 找出数组的最大公约数 问题本质 组合计数问题 数值计算问题 数学基础 质因数分解、组合数学、隔板法 数论、欧几里得算法 算法复杂度 中等至高（取决于实现） 低（线性时间） 实现难度 较高（需要多种数学知识） 低（ straightforward） 关键技巧 质因数分解、组合数预处理、乘法逆元 极值查找、辗转相除法 思维模式 创造性构建、组合思维 极值提取、共性寻找 应用场景 密码学、组合优化、概率计算 信号处理、资源分配、简化分数

深度对比洞察

这两个问题代表了算法设计中两种不同的思维范式：

构建式思维 vs 提取式思维：
第一个问题需要构建性思维——从基本构件（质因数）组合出复杂结构（数组）。这类似于建筑师从砖块建造房屋。第二个问题则需要提取性思维——从复杂集合中提取本质特征（最大公约数），这类似于雕塑家从巨石中雕出形态。

组合爆炸 vs 计算效率：
第一个问题面临组合爆炸的挑战——即使中等大小的输入也可能产生天文数字般的方案数，这要求我们使用巧妙的数学方法避免直接枚举。第二个问题则展示了如何通过深刻的数学洞察（欧几里得算法）实现超高效计算。

数学深度：
两个问题都涉及深刻的数学原理，但性质不同。第一个问题需要组合数学和数论的多方面知识，第二个问题则深入挖掘了整数性质的一个特定方面——可除性。

算法思维启示录

通过这两个问题的对比，我们可以得到许多算法设计的启示：

1. 简单问题不一定简单：第二个问题表面简单，但背后的欧几里得算法有着丰富的数学历史和深刻的理论基础

2. 数学是算法的基石：两个问题的高效解决都依赖于深厚的数学知识，而非单纯的编程技巧

3. 问题转化是关键：第一个问题的核心洞察是将乘积方案数问题转化为质因数分配问题

4. 边界情况的重要性：两个问题都需要仔细处理边界情况（如k=1或数组所有元素相等）

在这个数字主宰的时代，算法思维已经成为一种新的 literacy。今天探讨的两个问题虽然看似不同，但都展现了算法设计的精髓：将现实问题抽象为数学模型，寻找深刻的数学洞察，最终设计出高效的计算方案。

生成乘积数组的方案数问题教会我们，有时候最复杂的问题需要分解为最基本元素的组合；而找出最大公约数的问题提醒我们，本质往往隐藏在极端之中等待发掘。

无论是面对需要创造性组合的复杂问题，还是需要提取本质的简单问题，算法思维都为我们提供了强大的工具。下一次当你面临难题时，不妨问问自己：这是一个需要构建的问题，还是一个需要提取的问题？答案可能就在这个简单的区分之中。

记住，在算法的世界里，没有真正简单的问题——只有尚未被深刻理解的问题。每一个看似简单的算法背后，都可能隐藏着千百年来数学家的智慧结晶。

思考题留给大家：你能想到现实生活中哪些问题类似于第一个问题（需要组合基本元素），哪些类似于第二个问题（需要提取本质特征）？欢迎在评论区分享你的见解！

铃声库免费下载