题解 | #循环求和#

题目链接

循环求和

题目描述

牛牛把自然数中所有的偶数都添加了个负号，也就是说自然数变成了 1,-2,3,-4,5,-6... 的形式。于是牛牛想要计算一下，第 l 到 r 之间的数的和是多少。

输入:

第一行为一个整数 $T$ ，表示有 $T$ 组数据
接下来有 $T$ 行，每一行为两个整数 $l,r$

输出:

输出为 $T$ 行，每行表示每组数据的答案

解题思路

这是一个数学问题，可以通过以下步骤解决：

关键发现：
- 奇数保持为正数
- 偶数变为负数
- 需要计算区间 [l,r] 内所有数的和
解题策略：
- 分别计算奇数和偶数的贡献
- 奇数的和可以用等差数列公式
- 偶数的和也可以用等差数列公式，但要取负
具体步骤：
- 计算区间内奇数的个数和和
- 计算区间内偶数的个数和和
- 偶数和取负后与奇数和相加

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

// 计算区间[l,r]内的答案
long long solve(long long l, long long r) {
    long long sum = 0;
    
    // 处理奇数
    long long first_odd = (l % 2 == 0) ? l + 1 : l;
    long long last_odd = (r % 2 == 0) ? r - 1 : r;
    if(first_odd <= last_odd) {
        // 先除以2再乘以n，避免溢出
        sum += ((last_odd + first_odd) / 2) * ((last_odd - first_odd) / 2 + 1);
    }
    
    // 处理偶数
    long long first_even = (l % 2 == 0) ? l : l + 1;
    long long last_even = (r % 2 == 0) ? r : r - 1;
    if(first_even <= last_even) {
        // 先除以2再乘以n，避免溢出
        sum -= ((last_even + first_even) / 2) * ((last_even - first_even) / 2 + 1);
    }
    
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--) {
        long long l, r;
        cin >> l >> r;
        cout << solve(l, r) << '\n';
    }
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    // 计算区间[l,r]内的答案
    static long solve(long l, long r) {
        long sum = 0;
        
        // 处理奇数
        long firstOdd = (l % 2 == 0) ? l + 1 : l;
        long lastOdd = (r % 2 == 0) ? r - 1 : r;
        if(firstOdd <= lastOdd) {
            // 先除以2再乘以n，避免溢出
            sum += ((lastOdd + firstOdd) / 2) * ((lastOdd - firstOdd) / 2 + 1);
        }
        
        // 处理偶数
        long firstEven = (l % 2 == 0) ? l : l + 1;
        long lastEven = (r % 2 == 0) ? r : r - 1;
        if(firstEven <= lastEven) {
            // 先除以2再乘以n，避免溢出
            sum -= ((lastEven + firstEven) / 2) * ((lastEven - firstEven) / 2 + 1);
        }
        
        return sum;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            String[] parts = br.readLine().split(" ");
            long l = Long.parseLong(parts[0]);
            long r = Long.parseLong(parts[1]);
            out.println(solve(l, r));
        }
        out.flush();
    }
}

def solve(l, r):
    total = 0
    
    # 处理奇数
    first_odd = l + 1 if l % 2 == 0 else l
    last_odd = r - 1 if r % 2 == 0 else r
    if first_odd <= last_odd:
        # 先除以2再乘以n，避免溢出
        total += ((last_odd + first_odd) // 2) * ((last_odd - first_odd) // 2 + 1)
    
    # 处理偶数
    first_even = l if l % 2 == 0 else l + 1
    last_even = r if r % 2 == 0 else r - 1
    if first_even <= last_even:
        # 先除以2再乘以n，避免溢出
        total -= ((last_even + first_even) // 2) * ((last_even - first_even) // 2 + 1)
    
    return total

import sys
input = sys.stdin.readline
print = sys.stdout.write

T = int(input())
for _ in range(T):
    l, r = map(int, input().split())
    print(str(solve(l, r)) + '\n')

算法及复杂度

算法：数学（等差数列求和）
时间复杂度： $\mathcal{O}(T)$ - 每组数据只需要常数时间计算
空间复杂度： $\mathcal{O}(1)$ - 只需要常数空间存储变量

注意：

对于 $10^{18}$ 范围的数据，在计算过程中需要特别注意防止整数溢出
通过调整计算顺序（先除以2再乘以n）来避免中间结果溢出
添加快速输入输出优化以提高效率