12/04

SGU 106:The equation

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

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

\(x=x_0+k\left(\frac{b}{gcd(a,b)}\right)\;(k\in \mathbb Z)\)

\(y=y_0-k\left(\frac{a}{gcd(a,b)}\right)\;(k\in \mathbb Z)\)

这个公式有一点参数方程的味道,在算出两侧最大的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.
 

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

  1. victordu:呵呵,谢谢您的关注,不过貌似是您理解错了。
    题目让求的是解的个数,不要忘了这是一个二元方程,因此解是二元组的形式;当a、b中某一个为零的时候,即表示和它相乘的未知数不受限制,所以解应该是长度。
    不过我发现我的日志里面错别字很多呢,赶紧改改。
    如果您还有什么想法,欢迎您提出。

  2. “如果a和b有且仅有一个为零,借应该输出的时其在范围内的长度,而不是1“
    只有一个为零的时候是一个一元一次方程 当然只有一个解拉 糊涂了吧您