写在前面：《在数论及其应用——素数问题》一文中，笔者只是简单的介绍了一下拓展欧几里得算法可以解决同余问题，但没有详细的展开论述。这篇文章，就是针对数论中的同余问题，展开较为详细的探讨。
我们通过一个简单的题目，来进入关于同余问题的学习。(Problem source : pku 2769)
题目大意：给出n个数，你需要找出一个最小的m，使得这n个数中对m取模有n个不同的结果(任意两个数对m取模的结果不等)。
这道题不论从数理分析还是编程实现，都很基础，我们只是通过这个问题来初步了解一下什么是同余问题。
数理分析：这其实就是最基本的同余问题——a = b (mod m)。但是题目要求任意的两个数字不可同余，那么我们只需要排除掉所有同余情况即可。
编程实现：我们只需设置两层循环，对m由小到大进行穷举即可。穷举过程中，我们需要开设一个记录余数的布尔数组p，当穷举时算出余数为i，如果p[i] = 1，表明之前出现过此余数，那么就跳出循环寻找新的m。
参考代码如下。
#include<cstdlib>
#include<iostream>
#include<string.h>
using namespace std;
bool p[100001];
int d[1000001];
int main()
{
int ncases;
int num , i , j , k;
cin >> ncases;
while(ncases--)
{
cin >> num;
for(i = 0;i < num;i++)
cin >> d[i];
bool find;
for(i = 1;;i++)
{
memset(p , 0 , sizeof(p));
find = 1;
for(j = 0;j < num;j++)
{
if(p[d[j]%i])
{
find = 0;
break;
}
p[d[j]%i] = 1;
}
if(find)
break;
}
cout << i << endl;
}
return 0;
}
原文：http://www.cnblogs.com/rhythmic/p/5202879.html