1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此时Gcd(a',b')=1;
2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0，则n' * x0,n' * y0是方程a' * x + b' * y = n'的一组整数解；
3、根据数论中的相关定理，可得方程a' * x + b' * y = n'的所有整数解为：
x = n' * x0 + b' * t
y = n' * y0 - a' * t (t为整数)
上面的解也就是a * x + b * y = n 的全部整数解。
此时方程的所有解为：x=c*k1-b*t。
x的最小的可能值是0
§令x=0，可求出当x最小时的t的取值，但由于x=0是可能的最小取值，实际上可能x根本取不到0，那么由计算机的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中。 §求出的x可能会小于0，此时令t=t+1，求出的x必大于0；如果代回后x仍是大于等于0的，那么不需要再做修正。
//满足关系：(x + m * s) - (y + n *s) = k*l (k= 0 1 2
)即：(n - m)*s + l*k = x-y;
//利用拓展的欧几里得解出可能的s
#include <stdio.h>
#include <stdlib.h>
//求最大公约数
__int64 gcd (__int64 a, __int64 b)
{
if (b == 0)
return a;
else
gcd (b, a % b);
}
//求得满足 a*x + b*y = d；的x y
__int64 ex_Gcd (__int64 a, __int64 b, __int64 &x1, __int64 &y1)
{
if ( b == 0 )
{
x1 = 1;
y1= 0;
return a;
}
int r = ex_Gcd( b, a%b, x1, y1);
int temp = x1;
x1 = y1;
y1 = temp - a/b * y1;
}
int main ()
{
__int64 x, y, m, n, l;
int a, b, product, d;//a b 的最大公约数 product
int s, k;
__int64 s1, k1, s2, k2;
while ( scanf ("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &l ) != EOF )
{
a = n - m;
b = l;
d = x-y;
product = gcd (a,b);
if ( d % product != 0 )
printf ("Impossible\n");
else
{
a = a / product;
b = b / product;
d = d / product;
ex_Gcd (a, b, s1, k1); //得到(n-m)/product * s + l/product * k = 1;的 s k的解
s2 = d * s1; //得到(n-m)/product * s + l/product * k = d;的 s k的解
k2 = d * k1;
int t;
//s = s2 - b * t; 用下面的方法处理满足条件的解
//k = k2 - a * t;
t = s2 / b;
s = s2 - b * t;
if ( s <= 0)
{
s += b;
}
printf ("%d\n", s);
}
}
//system ("pause");
return 0 ;
}
posted on 2010-08-28 22:46
雪黛依梦 阅读(651)
评论(0) 编辑 收藏 引用 所属分类:
字符串处理题 、
数论