SGU 106:The equation

最近做了一下SGU106这道题，本来以为是一道很简单的数学题，结果就死活Accept不了……经过几个星期的奋战、参考了别人的程序终于解决了问题。

首先我们可以通过扩展欧几里德算法计算出符合该方程的一组解，之后根据数论推出的公式就可以的解数：

这个公式有一点参数方程的味道，在算出两侧最大的k以后相减即可。顺便说一句，我感觉上面我被链接解题报告的那位仁兄的程序似乎有些问题，尽管程序都能Accept，但我觉得他的理解有问题：在最开始的特殊情况判断的时候，如果a和b有且仅有一个为零，则应该输出的是其在范围内的长度，而不是1，Saratov State University没有在这里设点，因此没有出现问题。

我当初是ceil()/floor()这两个取整函数写错了，囧死了……其实PASCAL在竞赛的时候可以使用math库，里面都有。

program
        sgu106;
var
        i,j,k:int64;
        a,b,oa,ob,c,x1,x2,y1,y2:int64;
        x,y:int64;
        tx,ty:int64;
procedure swap(var a,b:int64);
        var
          t:int64;
        begin
          t:=a;
          a:=b;
          b:=t;
        end;
function min(a,b:int64):int64;
        begin
          if a>b
            then
              min:=b
            else
              min:=a;
        end;
function max(a,b:int64):int64;
        begin
          if a>b
            then
              max:=a
            else
              max:=b;
        end;
function ex_euclid(a,b:int64;var x,y:int64):int64;
        begin
          if b<>0
            then
              begin
                ex_euclid:=ex_euclid(b,a mod b,x,y);
                x:=x-(a div b)*y;
                swap(x,y);
              end
            else
              begin
                x:=1;
                y:=0;
                ex_euclid:=a;
              end;
        end;
function ceil(a,b:int64):int64;
        var
          c:int64;
        begin
          c:=a div b;
          if (a mod b)*b>0
            then
              ceil:=c+1
            else
              ceil:=c;
        end;
function floor(a,b:int64):int64;
        var
          c:int64;
        begin
          c:=a div b;
          if (a mod b)*b<0 then floor:=c-1 else floor:=c; end; begin readln(a,b,c); readln(x1,x2); readln(y1,y2); oa:=a; ob:=b; c:=-c; if (x1>x2)or(y1>y2)
          then
            begin
              writeln(0);
              halt;
            end;
        if (b=0)and(a=0)
          then
           begin
            if (c=0)
              then
                writeln(abs(x2-x1+1)*abs(y2-y1+1))
              else
                writeln(0);
            halt;
           end;
        if b=0
          then
           begin
            if (c mod a=0)and(c div a>=x1)and(c div a<=x2) then writeln(abs(y2-y1+1)) else writeln(0); halt; end; if a=0 then begin if (c mod b=0)and(c div b>=y1)and(c div b<=y2)
             then
              writeln(abs(x2-x1+1))
             else
              writeln(0);
            halt;
           end;
        tx:=1;
        ty:=1;
        if a<0
          then
            tx:=-tx;
        if b<0
          then
            ty:=-ty;
        if c<0
          then
            begin
              tx:=-tx;
              ty:=-ty;
            end;
        a:=abs(a);
        b:=abs(b);
        c:=abs(c);
        k:=ex_euclid(a,b,x,y);
        if c mod k<>0
          then
            begin
              writeln(0);
              halt;
            end;
        x:=x*c div k;
        y:=y*c div k;
        x:=x*tx;
        y:=y*ty;
        a:=oa div k;
        b:=ob div k;
        if (a<0)
          then
            swap(y1,y2);
        if (b<0) then swap(x1,x2); j:=max(ceil(x1-x,b),ceil(y-y2,a)); k:=min(floor(x2-x,b),floor(y-y1,a)); if k>=j
          then
            writeln(k-j+1)
          else
            writeln(0);
end.
 

*上述代码引用时请注明本文链接。