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
雪黛依夢 閱讀(662)
評論(0) 編輯 收藏 引用 所屬分類:
字符串處理題 、
數論