简介： 这一篇讨论一种欧几里德算法的经典应用。模线性方程，指形如：ax ≡ b(mod n) 的方程，在现实中有若干应用，例如在RSA公钥加密系统中的密钥查找。该方程可用扩展欧几里德算法求解，解的大小范围为[ 0 , n )。
算法： 运用扩展欧几里德算法解模线性方程其实是基于群论的，在这里不再赘述，如果把解的区间限制在整数范围内，那么方程有无穷解或者无解。因为无穷解在实际中并没有太大作用，所以我们一般考虑区间[ 0 , n )。 为了求解方程ax ≡ b(mod n)，我们需要把方程转化成下面形式： ax + ny = d , d = gcd(a , n) 如果d整除b，，那么存在方程存在d个解；否则无解。 方程ax + ny = d , d = gcd(a , n)可以使用扩展欧几里德算法求解，通过使用扩展欧几里德算法，我们可以求得最大公约数d以及方程的一组解(x , y)，若d整除b，我们可以通过这组解求得区间[ 0 , n )内的d个解。 首先我们需要求出最小解x0：
x%=n,x+=n,x%=n;ans[0]=x*(b/d)%(n/d);
之后在x0的基础上不断增加n/d并取模即可。
代码：
a,n){long long x,y;long long d=extend_gcd(a,n,x,y);vector<long long> ans;ans.clear();if(b%d==0){x%=n,x+=n,x%=n;ans.push_back(x*(b/d)%(n/d));for(long long i=1;i<d;i++)ans.push_back((ans[0]+i*n/d)%n);}return ans;}
extend_gcd函数的接口在这里！
听过许多故事，见过旅行风景，就这样，
