试题、程序及解题报告sgu sgu140

1、SGU140-eger Sequen解题北江中学【正文】一、问题描述给出 n 个整数a1,a2,.,an 和整数p,b，求一个整数数列x1,x2,.,xn，使得a1*x1+a2*x2+.+an*xnb (mod p)。若存在，第一行输出 YES，第二行输出这个数列。若不存在，输出 NO。二、问题分析这是一道关于模的数学问题。以两个数的时候为例。令 k1=(a,b)。（(a,b)表示 a 和 b 的最大公约数）。则可以用 a*x+b*y 表示出所有 k1 的倍数（其中 x,y 为变量）。若此时再引入一个数 c，令 k2=(k1,c)。则可以用 k1*t+c*z 表示出所有 k2的倍数。由于 k1

2、*t 是 k1 的倍数，因此可以用 a*x+b*y 的形式表示出来，也就是说可以用 a*x+b*y+c*z 的形式表示出所有 k2 的倍数。同理，按照上面的规律一直推下去，设 k=(a1,a2,.,an)，则可以用可以得a1*x1+a2*x2+.+an*xn 表示出所有 k 的倍数。如果 b 是 k 的倍数，则到一个满足题目要求的数列 x，否则无解。求数列 x 的方法如下：令 k=令 k1=(a1,a2,.,an)要求一个数列 x，使得 a1*x1+a2*x2+.+an*xn=k。(a1,a2,.,an-1)，并设 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了。而至于求数列 y，就是一个子问题了。求出 a1*x1+a2*x2+.+an*xn=k 的数列 x 后，题目的解。只需让 xi=xi*b/k 就能得到三、程序说明读入数据时可令 ai=ai mod p，可使数字不至于太大。Go(a,b)是求 a、b 的最大公约数 k 的函数，求的过程中会附带计算出 x,y，使 a*x+b*y=k。中途动态Ansi（即上面提到的 xi）的值，使它始

4、终到0,p-1中，这样可以避免数字过大，提高正确率。【附】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