3683: 荒岛野人-【2014暑期训练】T4Day2T2

同余方程及其在奥赛中的应用

    程序设计中，恰如其分的数学方法往往有助于算法的设计，起到优化程序的作用。

    同余方程及其解法是数论中的一个基本概念，有些试题表面看起来似乎属于盲目搜索类型，可一旦使用了同余方程等相关概念后，便可使求解过程既简便又高效。

    一、 同余方程及其解法

    同余方程，即：ax≡b(mod n) （n>0），表示ax mod n=b mod n，其中a、b、n为整数常量，x为未知量。

    求解同余方程式的根时，首先需了解：欧几里德（辗转相除法）推广算法。

    欧几里德递归定理：gcd(a,b)=gcd(b,a mod b)，实现用辗转相除的方法求两个正整数a、b的最大公约数。欧几里德推广算法不仅能求出两个正整数a、b的最大公约数d，而且还能计算出满足下式的整系数x和y

    d=gcd(a,b)=ax+by   (x与y可能为0或负数)

    我们知道，若b=0，可以返回最大公约数为a，x=1，y=0；若b<>0，可设d'=gcd(b,a mod b)=bx'+(a mod b)y'，则有：

d'= bx'+(a mod b)y'= bx'+(a-a div b*b)y'=ay'+b(x'-a div b* y')

∵ d=d'

∴ x=y'

      y= x'-a div b* y'

    这样，用辗转相除法求两个正整数a、b的最大公约数d的同时也可以生成满足等式：

     d=ax+by

的整系数x和y了。（实现该算法的PASCAL程序，详见实例程序）

function e_gcd(a,b:longint;var x,y:longint):longint;{欧几里德推广算法}

 var t:longint;

 begin if b=0 then

        begin e_gcd:=a;x:=1;y:=0;end

       else

        begin e_gcd:=e_gcd(b,a mod b,x,y);

              t:=x;x:=y;y:=t-(a div b)*y

        end

 end;

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：

的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。这时，如果 x₀ 是方程的一个解，那么所有的解可以表示为：

其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。

·                    在方程

3x ≡ 2 (mod 6)

中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。

·        在方程

5x ≡ 2 (mod 6)

中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。

·         在方程

4x ≡ 2 (mod 6)

中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2以及x=5。

    在欧几里德推广算法的基础上，我们可得同余方程ax≡b(mod n)的求解过程如下：

    通过欧几里德推广算法求出：

  d=gcd(a,n)和两个满足d=ax+ny的值x和y

    若b mod d<>0，则该方程无解；否则有d个解。其中第1个解为：

     x0=x*(b div d) mod n

    其余d-1个解为：

   xi=(x0+i*(n div d)) mod n  (1≤i≤d-1)

    同余方程ax＝b(mod n)的求解过程结束。

【题意分析】

    为了更好的理解题意，先举个简单的例子：有甲、乙两人在400米的环形跑道上顺时针跑步，甲的速度为V甲，乙的速度为V乙（V甲>V乙），起跑时，终点线顺时针到甲的跑道长度为L甲、到乙的跑道长度为L乙，设甲追到乙所需的时间为x，则有：（V甲-V乙）*x mod 400= (L乙-L甲) mod 400

    同样，原题中，若Pi>Pj且第i个野人与第j个野人过了x年会住在同一个山洞（假设寿命值无限），则必有：

（Pi-Pj）*x mod m=( Cj-Ci) mod m

    也即同余方程

           （Pi-Pj）*x ≡ Cj-Ci （mod m）………………（1）

有解。

    当然，仅仅是同余方程（Pi-Pj）*x ≡ Cj-Ci （mod m）有解还不能说明第i个野人与第j个野人在有生之年就会同住一个洞。因为该方程的解集中，如果不存在既小于第i个野人的寿命值Li又小于第j个野人寿命值Lj的正整数解，他们就不可能在有生之年同住一个洞——至少有一方在还没相遇就死去了。

    这样，题意即可理解为：找一个最小的m，使得任意两个野人在有生之年内，同余方程式（1）无解。

    搜索这样的m，可用穷举法。

    【程序参考】

const maxn=15;

var c,p,l:array[1..maxn] of longint;

    m,i,n:longint;

    fin,fout:text;

function e_gcd(a,b:longint;var x,y:longint):longint;{欧几里德推广算法}

 var t:longint;

 begin if b=0 then

        begin e_gcd:=a;x:=1;y:=0;end

       else

        begin e_gcd:=e_gcd(b,a mod b,x,y);

              t:=x;x:=y;y:=t-(a div b)*y

        end

 end;

function check:boolean;{判断当前的m是否合法}

 var  i,j,a,b,d,x,y,answer, md:longint;

 begin

   check:=false;

   for i:=1 to n do   {判断任意两个野人的情况}

    for j:=i+1 to n do

     begin a:=p[i]-p[j];b:=c[j]-c[i];

           if a<0 then begin a:=-a;b:=-b;end;{辗转相除法用于非负整数}

           d:=e_gcd(a,m,x,y);

           if b mod d=0 then  {同余方程有解的情况（无解即不可能冲突）}

            begin

               answer:=(x*b div d) mod m;  {第一个解}

               md:=m div d; {其它解可由第一个解加上md的倍数构成}

               while answer<0 do answer:=answer+md; {寻找最小正整数解}

               while answer>=md do answer:=answer-md;

if (answer<=l[i]) and (answer<=l[j]) then exit;

{条件成立，即第i个野人与第j个野人在有生之年会同住一个洞，不合法，退出本测试，继续m+1的测试}

            end;

     end;

   check:=true;

 end;

begin

  assign(fin,'savage.in');reset(fin);

  assign(fout,'savage.out');rewrite(fout);

  read(fin,n);

  m:=0;

  for i:=1 to n do

   begin read(fin,c[i],p[i],l[i]);

         dec(c[i]);

         if c[i]>m then m:=c[i];

   end;

  m:=m+1;

  while not check do m:=m+1;{从小到大，直到找到合法的m为止}

  writeln(fout,m);

  close(fin);

  close(fout);

end.