方程ax+by=c整数解的应用

方程ax+by=c整数解的应用

例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)＝1，c>b>a>0),现c筒装满水，
问能否在c筒个量出d升水(c>d>0)。若能，请列出一种方案。
算法分析：
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：
1.总有一个筒中的水没有变动；
2．不是一个筒被倒满就是另一个筒被倒光；
3．c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其
   它限制。

程序如下:

program mw;
type
node=array[0..1] of longint;
var
a,b,c:node;
d,step,x,y:longint;
function exgcd(a,b:longint;var x,y:longint):longint;
var t:longint;
begin
if b=0 then
  begin
   exgcd:=a;;x:=1;y:=0;
  end
  else
  begin
   exgcd:=exgcd(b,a mod b,x,y);
   t:=x;x:=y;y:=t-(a div b)*y
  end;
end;
procedure equation(a,b,c:longint;var x0,y0:longint);
var d,x,y:longint;
begin
d:=exgcd(a,b,x,y);
if c mod d>0 then
begin
  writeln('no answer');
  halt;
end else
begin
  x0:=x*(c div d);
  y0:=y*(c div d);
end;
end;
procedure fill(var a,b:node);
var t:longint;
begin
if a[1]<b[0]-b[1] then t:=a[1]
                  else t:=b[0]-b[1];
a[1]:=a[1]-t;
b[1]:=b[1]+t
end;
begin
write('a,b,c,d=');
readln(a[0],b[0],c[0],d);
equation(a[0],b[0],d,x,y);
step:=0;
a[1]:=0;b[1]:=0;c[1]:=c[0];
writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
if x>0 then
  repeat
   if a[1]=0 then fill(c,a) else
               if b[1]=b[0] then fill(b,c) else fill(a,b);
   inc(step);
   writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
  until c[1]=d
  else
   repeat
    if b[1]=0 then fill(c,b) else
             if a[1]=a[0] then fill(a,c) else fill(b,a);
    inc(step);
   writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);
   until c[1]=d;
end.