方法思路

1. 对于区间[l,r]内的所有数字，按顺序拼接成一个大数
2. 判断这个大数是否是3的倍数（即这个大数对3取余是否为0）
3. 由于拼接后的数可能非常大，我们使用模运算的性质：边拼接边取模

优化方案：

1. 直接计算区间内拼接数字的模3余数，避免大数运算
2. 利用数论知识：(a×10^n + b) mod 3 = ((a mod 3)×(10^n mod 3) + (b mod 3)) mod 3
3. 由于10^n mod 3 = 1（对任何n>0），可以进一步简化计算

代码实现

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        
        String[] nums = br.readLine().split(" ");
        int[] digitSums = new int[n];
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (char c : nums[i].toCharArray()) {
                sum += c - '0';
            }
            digitSums[i] = sum;
        }
        
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + digitSums[i - 1];
        }
        
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int total = prefix[r] - prefix[l - 1];
            out.println(total % 3 == 0 ? "YES" : "NO");
        }
        out.flush();
    }
}

Python

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n, q = map(int, input[ptr:ptr+2])
    ptr +=2
    nums = input[ptr:ptr+n]
    ptr +=n
    

    digit_sums = []
    for num in nums:
        total = 0
        for ch in num:
            total += int(ch)
        digit_sums.append(total)
    

    prefix = [0] * (n + 1)
    for i in range(1, n+1):
        prefix[i] = prefix[i-1] + digit_sums[i-1]
    

    output = []
    for _ in range(q):
        l, r = map(int, input[ptr:ptr+2])
        ptr +=2
        total = prefix[r] - prefix[l-1]
        if total % 3 == 0:
            output.append("YES")
        else:
            output.append("NO")
    
    print('\n'.join(output))

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<string> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    vector<int> digitSums(n);
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (char c : nums[i]) {
            sum += c - '0';
        }
        digitSums[i] = sum;
    }
    
    vector<int> prefix(n + 1);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + digitSums[i - 1];
    }
    
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        int total = prefix[r] - prefix[l - 1];
        cout << (total % 3 == 0 ? "YES" : "NO") << '\n';
    }
    
    return 0;
}