解题思路

对于每一轮需要计算的奇数和，我们可以使用等差数列求和公式：

  1. 对于奇数 ，从 到 的奇数和为：
  2. 对于偶数 ，从 到 的奇数和为：

这样就避免了使用循环来累加奇数，大大提高了效率。

代码

#include <iostream>
using namespace std;
int main() {
    long long n = 0;
    while (cin >> n) {
        long long sum = 0;
        while(n > 0) {
            if(n % 2 == 1) {
                // 奇数情况：(n+1)(n/2+1)/2
                sum += (n + 1) * (n / 2 + 1) / 2;
            } else {
                // 偶数情况：n*n/4
                sum += n * n / 2 / 2;
            }
            n = n / 2;
        }
        cout << sum << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            long n = sc.nextLong();
            long sum = 0;
            
            while(n > 0) {
                if(n % 2 == 1) {
                    // 奇数情况：(n+1)(n/2+1)/2
                    sum += (n + 1) * (n/2 + 1) / 2;
                } else {
                    // 偶数情况：n*n/4
                    sum += n * n / 2 / 2;
                }
                n = n / 2;
            }
            System.out.println(sum);
        }
    }
}

while True:
    try:
        n = int(input())
        sum = 0
        
        while n > 0:
            if n % 2 == 1:
                # 奇数情况：(n+1)(n/2+1)/2
                sum += (n + 1) * (n//2 + 1) // 2
            else:
                # 偶数情况：n*n/4
                sum += n * n // 4
            n = n // 2
            
        print(sum)
    except EOFError:
        break

算法及复杂度

  • 算法：使用等差数列求和公式来计算每轮的奇数和。
  • 时间复杂度：，其中N是输入的数字。每次除以2，只需要次运算。
  • 空间复杂度：，只使用了常数额外空间。