新浪博客

线性同余方程的解法

2011-07-18 19:38阅读：

http://blog.sina.cn/dpool/blog/u/2102224794

对于方程：ax≡b(mod m)，a、b、m都是整数，求解x的值。
例题：poj 1061 青蛙的约会
符号说明：
mod表示：取模运算
ax≡b(mod m)表示：ax-b≡0（
mod m），即同余
gcd(a,b)表示：a和b的最大公约数
分析过程：
问题一：求解最大公约数。
古老的解法是欧几里德法，即辗转相除法：gcd(a,b)=gcd(b,a mod b)。
问题二：存在x、y使得ax+by=gcd(a,b)；
ax+by=gcd(a,b)=gcd(b,a mod b)
=b*x'+(a-[a/b]*b)*y' ([]表示取整)
=a*y'+b*(x'-[a/b]*y')
则：
x=y';
y=x'-[a/b]*y';
问题三：ax≡b(mod m)的求解。
首先，gcd(a,m)必须整除b，否则方程无解。
其次，当gcd(a,m)=1时，存在x0,y0使得x0*a+y0*m=1,令x=b*x0,然后mod m。可得在[0,m)上的唯一解。
最后，当d=gcd(a,m)>1时，考虑方程：a/d *x=b/d (mod m/d)。可得一解x属于[0,m/d)。原方程有d个解：x,x+m/d,x+2m/d,……,x+(d-1)m/d。
程序如下：
#include<iostream>
struct triple
{
int gcd,x,y;
};
int mod(int a,int b)//取模运算a mod b
{
if(a>=0) return a%b;
else return a%b+b;
}
triple ex_Euclid(int a,int b)//扩展欧几里德算法，求最大公约数和x、y使得x*a+y*b=(a,b)
{
triple result,temp;
if(b==0)
{
result.gcd=a;
result.x=1;
result.y=0;
}
else
{
temp=ex_Euclid(b,mod(a,b));
result.gcd=temp.gcd;
result.x=temp.y;
result.y=temp.x-(a/b)*temp.y;
}
return result;
}
void MLCE(int a,int b,int m)//线性同余方程ax≡b(mod n)求解
{
triple temp=ex_Euclid(a,m);
if(b%temp.gcd!=0)
{
printf('方程无解');return;
}
int x=mod(temp.x*b/temp.gcd,m/temp.gcd);//满足方程的最小的非负整数
if(temp.gcd==1)
printf('方程有1个解属于[0,%d):x=%d',m,x);
else
{
printf('方程有%d个解属于[0,%d):',temp.gcd,m);
for(int i=0;i<temp.gcd;i++)
printf('x[%d]=%d',i+1,x+i*m/temp.gcd);
}
}
int main()
{
int a,b,m;
scanf('%d%d%d',&a,&b,&m);
MLCE(a,b,m);
system('pause');
return 0;
}

我的更多文章

下载客户端阅读体验更佳

APP专享