牛客12579题解析：递归求解1~N最大奇约数之和的优化解法
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506041749051324298458.jpg一、解题思路采用递归策略，巧妙将问题分解为奇数和偶数部分：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. 合并输出：返回奇偶部分和。三、代码与注释
#include <iostream>
using namespace std;
// 递归计算1~N的最大奇约数和
long long calculateSum(int N) {
if(N < 1) return 0;// 边界条件处理
long long odd_cnt = (N + 1) / 2;// 奇数个数
long long odd_sum = odd_cnt * odd_cnt;// 等差数列求和
return odd_sum + calculateSum(N / 2);// 递归叠加偶数部分
}
int main() {
int N;
while(cin >> N) {// 处理多组输入
if(N <= 0) {
cout << 0 << endl;
continue;
}
cout << calculateSum(N) << endl;
}
return 0;
}原文：牛客12579题解析：递归求解1~N最大奇约数之和的优化解法
页:
[1]