試題、程序及解題報告sgu sgu140

1、SGU140-eger Sequen解題北江中學(xué)【正文】一、問題描述給出 n 個整數(shù)a1,a2,.,an 和整數(shù)p,b，求一個整數(shù)數(shù)列x1,x2,.,xn，使得a1*x1+a2*x2+.+an*xnb (mod p)。若存在，第一行輸出 YES，第二行輸出這個數(shù)列。若不存在，輸出 NO。二、問題分析這是一道關(guān)于模的數(shù)學(xué)問題。以兩個數(shù)的時候為例。令 k1=(a,b)。（(a,b)表示 a 和 b 的最大公約數(shù)）。則可以用 a*x+b*y 表示出所有 k1 的倍數(shù)（其中 x,y 為變量）。若此時再引入一個數(shù) c，令 k2=(k1,c)。則可以用 k1*t+c*z 表示出所有 k2的倍數(shù)。由于 k1

2、*t 是 k1 的倍數(shù)，因此可以用 a*x+b*y 的形式表示出來，也就是說可以用 a*x+b*y+c*z 的形式表示出所有 k2 的倍數(shù)。同理，按照上面的規(guī)律一直推下去，設(shè) k=(a1,a2,.,an)，則可以用可以得a1*x1+a2*x2+.+an*xn 表示出所有 k 的倍數(shù)。如果 b 是 k 的倍數(shù)，則到一個滿足題目要求的數(shù)列 x，否則無解。求數(shù)列 x 的方法如下：令 k=令 k1=(a1,a2,.,an)要求一個數(shù)列 x，使得 a1*x1+a2*x2+.+an*xn=k。(a1,a2,.,an-1)，并設(shè) a1*y1+a2*y2+.+an-1*yn-1=k1。因為(k1,an)=k，

3、可以求出 k1*s+an*t=k 中的 s 和 t 。只需要令 xi=yi*s ， 就能使a1*x1+a2*x2+.+an-1*xn-1=k1*s。再令 xn=t，就能滿足 a1*x1+a2*x2+.+an*xn=k了。而至于求數(shù)列 y，就是一個子問題了。求出 a1*x1+a2*x2+.+an*xn=k 的數(shù)列 x 后，題目的解。只需讓 xi=xi*b/k 就能得到三、程序說明讀入數(shù)據(jù)時可令 ai=ai mod p，可使數(shù)字不至于太大。Go(a,b)是求 a、b 的最大公約數(shù) k 的函數(shù)，求的過程中會附帶計算出 x,y，使 a*x+b*y=k。中途動態(tài)Ansi（即上面提到的 xi）的值，使它始

4、終到0,p-1中，這樣可以避免數(shù)字過大，提高正確率。【附】140.pasProgram Sgu_140;Const Maxn=100;Var i,j,k,m,n,p,b,x,y,z,k1:Long;Num:array1.MaxnAns:array1.Maxnof Long;of Extended;Function Go(a,b:Long):Long;Var k:Long Beginif b=0 then beginGo:=a;x:=1;y:=0;end else begin;Go:=Go(b,a mod b); k:=y;y:=x-(a div b)*y; x:=k;end;End;Proce

5、dure Pr;Var i:LongBegin;wrin(YES);for i:=1 to n do write(Ansi:0:0, ); wrin;halt;End;Beginreadln(n,p,b); for i:=1 to n do beginread(Numi);Numi:=Numi mod p; end;Fillchar(Ans,sizeof(Ans),0); k:=p;k1:=p;for i:=1 to n do Beginif Numik then k:=Go(Numi,k)else begink:=Go(k,Numi); z:=x;x:=y;y:=z; end;if kk1 then beginAnsi:=x;if Ansi0 then Ansi:=(-Ansi+p-1)/p)*p+Ansielse Ansi:=Ansi- for j:=1 to i-1 do BeginAnsj:=Ansj*y;(Ansi/p)*p;if Ansj0 then Ansj:=(-Ansj+p-1)/p)*p+Ansjelse Ansj:=Ansj-(Ansj/p)*p; End;k1:=k; end;if abs(b div k-b/k)1e-10 then beginfor