求解对n个不同整数做除法余数互异的最小整数m的算法

核心性质转化 #

首先明确模运算的基本等价结论：两个整数a、b模m余数相同的充要条件是m能整除两数的绝对差值|a-b|。
回到题目要求：所有数模m的余数两两不同，本质就是m不能整除集合中任意两个不同元素的绝对差值。
这个转化直接把原问题从余数校验变成了差值整除性判断，是整个解法的核心。

具体算法步骤 #

• 预处理输入的整数集合S（题目已说明元素互不相同，无需额外去重）。
• 计算S中所有两两元素的绝对差值，存入去重集合D，重复的差值不需要重复存储，不会影响判断结果。
• 从题目给出的下界m = n开始，从小到大逐个校验m的合法性：
  • 校验规则：遍历D中的差值，若存在某个差值d满足d % m == 0，说明当前m会让差为d的两个数同余，m不合法，直接跳出校验尝试下一个m；如果所有差值都不满足该条件，当前m就是最小解，直接返回即可。

校验优化：对于任意差值d < m，d % m = d必然大于0，不可能被m整除，因此校验时可以直接跳过所有小于m的差值，只检查大于等于m的d即可，能大幅减少计算量。

正确性说明 #

我们从最小的可能下界n开始从小到大枚举，第一个满足“不整除任何两两差值”的m自然就是全局最小解。同时题目已经保证解必然存在：当m大于集合中最大的两两差值（即m > max(S) - min(S)）时，所有差值都小于m，不可能被m整除，此时m一定合法，因此枚举过程必然会终止。

示例演示 #

比如输入集合S = {1,2,4}，n=3：

1. 计算两两绝对差：|1-2|=1、|1-4|=3、|2-4|=2，去重后D={1,2,3}
2. 从m=3开始校验：D中≥3的差值是3，3%3 == 0，说明m=3不合法（1和4模3均为1，余数重复）
3. 尝试m=4：D中所有差值都小于4，没有d能被4整除，因此m=4就是最小解，实际计算余数：1 mod4=1、2mod4=2、4mod4=0，确实两两不同。

进阶优化方向 #

如果n的规模较大，O(n²)枚举所有两两差的开销过高，可以用FFT快速计算所有可能存在的差值，替代O(n²)的双重循环；如果差值范围不大，也可以用筛法提前标记所有不合法的m（即所有能整除至少一个差值的≥n的正整数），直接找到第一个未被标记的m即可，进一步提升速度。
这个解法完全兼容输入包含负整数的场景：因为判断逻辑基于差值的整除性，和元素本身的正负无关，不受不同编程语言负数取模实现差异的影响。

内容的提问来源于stack exchange，提问作者TheCodeDemon