牛客12579题解析：递归求解1~N最大奇约数之和的优化解法

19339201706

一、解题思路

采用递归策略，巧妙将问题分解为奇数和偶数部分：

1. 奇数部分：利用等差数列求和公式。1到N的奇数和为前k个奇数的和（k=(N+1)/2），即k^2。

2. 偶数部分：递归调用calculateSum(N/2)，因偶数因子可视为1~N/2的因子扩展（如2x的因子包含x的因子）。

3. 边界处理：N<1时直接返回0，多组输入用循环接收。

二、解题步骤

1. 输入处理：循环读取N，若N≤0输出0并跳过。

2. 计算奇数部分：通过(N+1)/2获取奇数个数，平方求和。

3. 递归计算偶数部分：调用calculateSum(N/2)，叠加结果。

4. 合并输出：返回奇偶部分和。

三、代码与注释

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. // 递归计算1~N的最大奇约数和
   
5. long long calculateSum(int N) {
   
6.     if(N < 1) return 0;  // 边界条件处理
   
7.     long long odd_cnt = (N + 1) / 2;  // 奇数个数
   
8.     long long odd_sum = odd_cnt * odd_cnt;  // 等差数列求和
   
9.     return odd_sum + calculateSum(N / 2);  // 递归叠加偶数部分
   
10. }
    
11. 
    
12. int main() {
    
13.     int N;
    
14.     while(cin >> N) {  // 处理多组输入
    
15.         if(N <= 0) {  
    
16.             cout << 0 << endl;
    
17.             continue;
    
18.         }
    
19.         cout << calculateSum(N) << endl;
    
20.     }
    
21.     return 0;
    
22. }

复制代码

原文：牛客12579题解析：递归求解1~N最大奇约数之和的优化解法