【数据结构】



　　考虑到此题的测试数据可能较大，故采用一Record型变量储存数组，其中：Len表示当前数值的位数，Byte型数组Data[1..Maxn]储存数值各位上的数字。



【问题分析】



　　首先，先计算得到的数a与k相乘后的各位数字和s。因为题目中的k在场整形范围内，故只需将数组a.Data内的各位数字由低至高乘以k后取个位数字，剩余的数进位至下一位，再将此时的a.Data中各位数字相加，之和即为s。



　　现在，题目变为：已知数A与s，求另一数C，使其各位数字之和为s，并且C是符合此条件的最小的数。考虑用以下算法：



　　建一Shortint型数组d[0..Maxn]，从此数组的第一位（即d[1]）开始，取a.Data[i]的值（i为此时取的位数），同时把s减去a.Data[i]的值。



　　当发现s的值小等于零时，将d[i]的值取为d[i]+s-1，并将d[i-1]的值加一，如果di-1]的值大于9则进位（具体操作参看下文加下划线文字），并将数组的下一位置末尾的值都赋为零，再将数组中从第i位至末位的数进行变换。具体操作为：第i位的数与末位数调换位置，第i-1位与倒数第二位调换……即可。



例：A=129945，s=23。



　　首先对数组d各项赋值，依次为：1，2，9，9，赋值至第5项时，d[5]=4，而s= -2<0，故d[5]=4+s=4+(-2)=2，对d[4]进行进位操作，d[6]取零后得到新数：139910，将"9910"变换操作后得数130199即为正确答案。

　　当取遍数组后，如果s的值大于零，则将数组的最后一位（即数值的个位）与s相加。如果此时数组的最后一位大于9，则把数组的最后一位赋值为9，将它与9的差与它的前一位相加，一直到某一位不超过9为止（当a[1]>9时，进位至a[0]，并将数组往后移一位）。这里有个技巧：可将数组设为d[-10..Maxn]，再建一变量ｔ，数组需要后移时，把ｔ的值加１，最后根据ｔ的值移位，可减少程序的运算量。



例：A=129945，s=43。



　　首先对数组d各项赋值，依次为：1，2，9，9，4，5。此时已赋值完毕，而s=13，进位操作后得新数169999即位正确答案。

　　再将a赋值为求得的数，循环(n-1)次，即可。



【参考程序】



　Program number;

　　Const

　　　inputfilename='numbers.in2';

　　　outputfilename=''{'numbers.out'};

　　　Maxn=5000;

　　TYPE

　　　num=RECORD

　　　　len:integer;

　　　　data:array[1..maxn]of 0..9;

　　　　　　end;

　　Var

　　　a:num;

　　　k,n,h:longint;

　　Procedure readdata;

　　　var f:text;

　　　　c:array[0..maxn] of 0..9;

　　　　str,i:longint;

　　Begin

　　　assign(f,inputfilename);

　　　reset(f);

　　　readln(f,str,k,n);

　　　　a.len:=0;

　　　　while str>0 do

　　　　　begin

　　　　　　inc(a.len);

　　　　　　　a.data[a.len]:=str mod 10;

　　　　　　　str:=str div 10;

　　　　　end;

　　　　　for i:=1 to a.len do c[i]:=a.data[a.len-i+1];

　　　　　for i:=1 to a.len do a.data[i]:=c[i];

　　　　close(f);

　　　End;

　　Procedure gettotal;

　　　var

　　　　i,t:longint;

　　Begin

　　　h:=0;

　　　t:=0;

　　　　for i:=a.len downto 1 do

　　　　　begin

　　　　　　t:=longint(a.data[i])*k+t;

　　　　　　inc(h,t mod 10);

　　　　　　t:=t div 10;

　　　　　end;

　　　　while t>0 do

　　　　　begin

　　　　　　inc(h,t mod 10);

　　　　　　t:=t div 10;

　　　　　end;

　　　　End;

　　Procedure doing;

　　　var

　　　　i,j,jj,q,t,u,uu:longint;

　　　　c:array[-10..maxn] of integer;

　　　　d:array[1..50] of integer;

　　　Begin

　　　　for t:=2 to n do

　　　　　begin

　　　　　　fillchar(c,sizeof(c),0);

　　　　　　fillchar(d,sizeof(d),0);

　　　　　　gettotal;

　　　　　　j:=0; jj:=0; i:=a.len;

　　　　　　while (h>0) and (j<=a.len) do

　　　　　　　begin

　　　　　　　　inc(j);

　　　　　　　　c[j]:=a.data[j];

　　　　　　　　h:=h-c[j];

　　　　　　　　if h<=0 then

　　　　　　　　　begin

　　　　　　　　　　c[j]:=c[j]+h;

　　　　　　　　　　jj:=j;

　　　　　　　　　end;

　　　　　　　　end;

　　　　　　　if jj>0 then

　　　　　　　　begin

　　　　　　　　　q:=jj;

　　　　　　　　　inc(c[jj-1]);

　　　　　　　　　dec(c[jj]);

　　　　　　　　　while c[jj-1]>9 do

　　　　　　　　　　begin

　　　　　　　　　　c[jj-2]:=c[jj-2]+c[jj-1]-9;

　　　　　　　　　　c[jj-1]:=9;

　　　　　　　　　　dec(q);

　　　　　　　　　　dec(jj);

　　　　　　　　　end;

　　　　　　　　jj:=c[q]; h:=0;

　　　　　　　　for j:=q to a.len do

　　　　　　　　　begin

　　　　　　　　　　inc(h);

　　　　　　　　　　d[h]:=c[j];

　　　　　　　　　　end;

　　　　　　　　　for j:=h downto 1 do

　　　　　　　　　c[q+h-j]:=d[j];

　　　　　　　　end

　　　　　　　else

　　　　　　　　begin

　　　　　　　　　c[i]:=c[i]+h;

　　　　　　　　　while c[i]>9 do

　　　　　　　　　　begin

　　　　　　　　　　　c[i-1]:=c[i-1]+c[i]-9;

　　　　　　　　　　　c[i]:=9;

　　　　　　　　　　　dec(i);

　　　　　　　　　　end;

　　　　　　　　end;

　　　　　　　uu:=-10;

　　　　　　　while c[uu]=0 do inc(uu);

　　　　　　　u:=a.len-uu+1;

　　　　　　　q:=1-uu;

　　　　　　　　for i:=1 to u do a.data[i]:=c[i-q];

　　　　　　　　a.len:=u;

　　　　　　　end;

　　　　　　End;

　　　　　　Procedure print;

　　　　　　　var f:text; i:longint;

　　　　　　Begin

　　　　　　　assign(f,outputfilename);

　　　　　　　rewrite(f);

　　　　　　　for i:=1 to a.len do write(f,a.data[i]);

　　　　　　　writeln(f);

　　　　　　　close(f);

　　　　　　End;

　　　　　　Begin

　　　　　　　readdata;

　　　　　　　doing;

　　　　　　　print;

　　　　　　End.