题解思路

这是一道典型的二分查找结合模运算优化问题，核心在于利用模运算的循环性质和双候选搜索策略，将朴素的O(nm)算法优化为O((n+m)log m)。

核心算法分析

问题转换思路： 对于固定的A[i]，我们需要在B数组中找到最优的B[j]，使得(A[i] + B[j]) % mod最小。

关键数学洞察： 设a = A[i] % mod，我们希望找到b使得(a + b) % mod最小。考虑模运算的性质：

• 如果a + b < mod，则(a + b) % mod = a + b
• 如果a + b ≥ mod，则(a + b) % mod = a + b - mod

最优性分析： 对于固定的a，最优的b有两个候选：

1. 第一类候选：使得a + b刚好等于或略大于mod的最小b
2. 第二类候选：使得a + b刚好小于mod的最大b

这两个候选分别对应：

1. 最小的使得(a + b) % mod ≥ 0的情况
2. 最大的使得(a + b) % mod < mod的情况

双候选策略设计：

目标值计算：

long targetValue = (modulus - currentA + modulus) % modulus;

这个目标值是使得(currentA + b) ≡ 0 (mod modulus)的理想b值。

二分查找应用：

int position = Collections.binarySearch(sortedB, targetValue);
if (position < 0) {
    position = -(position + 1); // 转换为插入位置
}

// 候选1：第一个 >= targetValue的元素
long candidate1 = sortedB.get(position % m);

// 候选2：最后一个 < targetValue的元素  
long candidate2 = sortedB.get((position - 1 + m) % m);

循环数组处理技巧： 由于模运算的循环性，我们可以将B数组视为循环数组，通过取模操作优雅地处理边界情况。

详细算法设计

预处理阶段：

// 对B数组元素取模并排序
List<Long> processedB = new ArrayList<>();
for (int i = 0; i < m; i++) {
    processedB.add(arrayB[i] % modulus);
}
Collections.sort(processedB);

主要搜索逻辑：

long globalMinimum = modulus;

for (int i = 0; i < n; i++) {
    long normalizedA = arrayA[i] % modulus;
    long complementTarget = (modulus - normalizedA) % modulus;
    
    // 二分查找最接近的两个候选值
    int insertPos = Collections.binarySearch(processedB, complementTarget);
    if (insertPos < 0) {
        insertPos = -(insertPos + 1);
    }
    
    // 检查两个关键候选
    long firstCandidate = processedB.get(insertPos % m);
    long secondCandidate = processedB.get((insertPos - 1 + m) % m);
    
    long option1 = (normalizedA + firstCandidate) % modulus;
    long option2 = (normalizedA + secondCandidate) % modulus;
    
    globalMinimum = Math.min(globalMinimum, Math.min(option1, option2));
    
    if (globalMinimum == 0) break; // 提前终止优化
}

复杂度分析：

• 预处理：O(m log m)
• 主循环：O(n log m)
• 总体复杂度：O((n+m) log m)
• 空间复杂度：O(m)

Java代码实现

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

public class Main {
    
    private static long findOptimalModSum(int n, int m, long modulus, 
                                        long[] arrayA, long[] arrayB) {
        
        // 预处理：对数组B的所有元素取模并排序
        List<Long> normalizedSortedB = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            normalizedSortedB.add(arrayB[i] % modulus);
        }
        Collections.sort(normalizedSortedB);
        
        long optimalResult = modulus; // 初始化为不可能的大值
        
        // 遍历数组A的每个元素
        for (int i = 0; i < n; i++) {
            long normalizedA = arrayA[i] % modulus;
            
            // 计算理想的B值，使得(A + B) ≡ 0 (mod modulus)
            long idealBValue = (modulus - normalizedA) % modulus;
            
            // 使用二分查找定位最接近idealBValue的位置
            int searchResult = Collections.binarySearch(normalizedSortedB, idealBValue);
            int candidatePosition;
            
            if (searchResult >= 0) {
                // 精确匹配，直接返回0
                return 0;
            } else {
                // 转换为插入位置
                candidatePosition = -(searchResult + 1);
            }
            
            // 检查两个关键候选值
            
            // 候选1：第一个大于等于idealBValue的元素
            long upperCandidate = normalizedSortedB.get(candidatePosition % m);
            long upperResult = (normalizedA + upperCandidate) % modulus;
            
            // 候选2：最后一个小于idealBValue的元素
            long lowerCandidate = normalizedSortedB.get((candidatePosition - 1 + m) % m);
            long lowerResult = (normalizedA + lowerCandidate) % modulus;
            
            // 更新全局最优值
            optimalResult = Math.min(optimalResult, Math.min(upperResult, lowerResult));
            
            // 提前终止条件
            if (optimalResult == 0) {
                break;
            }
        }
        
        return optimalResult;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
        String[] parameters = reader.readLine().split(" ");
        int n = Integer.parseInt(parameters[0]);
        int m = Integer.parseInt(parameters[1]);
        long mod = Long.parseLong(parameters[2]);
        
        String[] aElements = reader.readLine().split(" ");
        long[] arrayA = new long[n];
        for (int i = 0; i < n; i++) {
            arrayA[i] = Long.parseLong(aElements[i]);
        }
        
        String[] bElements = reader.readLine().split(" ");
        long[] arrayB = new long[m];
        for (int i = 0; i < m; i++) {
            arrayB[i] = Long.parseLong(bElements[i]);
        }
        
        long result = findOptimalModSum(n, m, mod, arrayA, arrayB);
        System.out.println(result);
        
        reader.close();
    }
}

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class ModularSumOptimizer {
private:
   vector<long long> processedArray;
   long long modulusValue;
   int arraySize;
   
public:
   long long solve(const vector<long long>& setA, const vector<long long>& setB, long long mod) {
       modulusValue = mod;
       arraySize = setB.size();
       
       // 预处理：对数组B取模并排序
       processedArray.clear();
       processedArray.reserve(arraySize);
       
       for (int i = 0; i < arraySize; i++) {
           processedArray.push_back(setB[i] % modulusValue);
       }
       
       sort(processedArray.begin(), processedArray.end());
       
       long long globalOptimum = modulusValue;
       
       // 遍历数组A的每个元素
       for (size_t i = 0; i < setA.size(); i++) {
           long long currentElement = setA[i] % modulusValue;
           
           // 计算使得(currentElement + target) ≡ 0 (mod modulusValue)的目标值
           long long targetComplement = (modulusValue - currentElement) % modulusValue;
           
           // 二分查找：寻找最接近targetComplement的位置
           auto lowerBoundIter = lower_bound(processedArray.begin(), 
                                           processedArray.end(), 
                                           targetComplement);
           
           // 计算位置索引
           int candidateIndex = lowerBoundIter - processedArray.begin();
           
           // 检查两个候选值
           
           // 候选1：第一个大于等于target的元素（循环处理）
           long long candidate1 = processedArray[candidateIndex % arraySize];
           long long result1 = (currentElement + candidate1) % modulusValue;
           
           // 候选2：最后一个小于target的元素（循环处理）
           long long candidate2 = processedArray[(candidateIndex - 1 + arraySize) % arraySize];
           long long result2 = (currentElement + candidate2) % modulusValue;
           
           // 更新全局最优解
           globalOptimum = min({globalOptimum, result1, result2});
           
           // 提前退出优化
           if (globalOptimum == 0) {
               return 0;
           }
       }
       
       return globalOptimum;
   }
};

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   
   int n, m;
   long long mod;
   cin >> n >> m >> mod;
   
   vector<long long> arrayA(n), arrayB(m);
   
   for (int i = 0; i < n; i++) {
       cin >> arrayA[i];
   }
   
   for (int i = 0; i < m; i++) {
       cin >> arrayB[i];
   }
   
   ModularSumOptimizer optimizer;
   long long result = optimizer.solve(arrayA, arrayB, mod);
   
   cout << result << endl;
   
   return 0;
}

时间复杂度：O((n+m) log m)，排序O(m log m) + n次二分查找O(n log m) 空间复杂度：O(m)，用于存储处理后的B数组