【问题描述】乐乐是一个聪明而又勤奋好学的孩子。
他总喜欢探求事物的规律。
一天，他突然对数的正整数次幂产生了兴趣。
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度)。
类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环?如果循环的话，循环长度是多少呢?注意：1.如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2.如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。
【输入文件】输入文件circle.in只有一行，包含两个整数n(1≤n< 10100)和k(1≤k≤100)，n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。
如果循环不存在，输出-1。
【样例输入】32 2【样例输出】4【数据规模】对于30%的数据，k≤4；对于全部的数据，k≤00。
从个位开始判断:几轮循环后,如果出现1(个位数字的第1次),计算循环长度j,连续自乘幂j次,转(2)；如果没有出现1,出现了其它数字,则循环节不存在,输出-1后结束。
(1)依次判断十位……。
(2)每个数字的循环长度纪录在circle数组。
(3)如果能计算至最高位,则circle数组的每1个元素连乘就是要求的n的正整数次幂的最后k位的循环长度。
32的循环长度=4，但程序是先判断个位成立后sc:=ss;ij:=b[a[j,i]];circLe[i]:=j-1;{循环长度=幂次方-1，并记录在circle数组里,circle[1]=5-1=4}for ij:=2 to j-1 do muLti(ss,sc,ss);{初值ss=32,经过ss自乘3次=104876,在十位乘1次=33554432, circle[2]=1}circle[1] *circle[2]=4*1=4const max=100;type hint=array[0..max]of Longint;var st,s1,s2:string; k,ok:Longint;a:array[1..11]of hint;{某1位的循环长度一定<11,在第11次乘幂不能出现初始值,则循环不成立} b:array[0..9]of Longint;circLe:array[0..max]of Longint;tot:hint;n,start:hint; sc,ss:hint;i,j,ij,L,m:Longint;procedure muLti(var a:hint;b,c:hint);var i,j,e:Longint;beginfiLLchar(a,sizeof(a),0);for i:=0 to k-1 dofor j:=0 to k-1 doif i+j<=k-1 then inc(a[i+j],b[i]*c[j]);e:=0;for i:=0 to k-1 do begina[i]:=a[i]+e;e:=a[i] div 10;a[i]:=a[i] mod 10;end;end;procedure muLt(var a:hint; b:Longint);var i,e:Longint;beginfor i:=0 to a[max] do a[i]:=a[i]*b;e:=0;for i:=0 to a[max]+1 do begina[i]:=a[i]+e;e:=a[i] div 10;a[i]:=a[i] mod 10;end;if a[a[max]+1]>0 then a[max]:=a[max]+1;end;beginassign(input,'circLe.in'); reset(input);assign(output,'circLe.out'); rewrite(output);readLn(st);s1:=copy(st,1,pos(' ',st)-1); deLete(st,1,pos(' ',st)); s2:=st;{ s1= st的第一个至空格前所有字符，赋值后，删除st的第一个至空格所有字符，s2= st空格后所有字符}deLete(st,1,pos(' ',st)-1);s2:=st; whiLe pos(' ',s2)>0 do deLete(s2,pos(' ',s2),1);{赋值后，删除st的第一个至第一个空格所有字符，s2= st空格后所有字符，可能存在连续空格}vaL(s2,k,ok); {字符型S2转换为数值型K}s2:=copy(s1,Length(s1)-k+1,k); {S1后长度k-1位赋值给S2}whiLe Length(s2)<k do s2:='0'+s2; {如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0}for i:=1 to k do n[k-i]:=ord(s2[i])-48; {S1后长度k-1位转换为数值型n[k-i]}n[max]:=k-1; {求字符型S2长度}start:=n; ss:=n; a[1]:=n; {n,ss,start都是一维数组hint, a是二维数组,直接赋值一行数据 a[1]是个一维数组}for i:=0 to k-1 dobegin {b:array[0..9]of Longint}fiLLchar(b,sizeof(b),0); b[a[1,i]]:=1; {第i位数字第1次出现,假设b[a[1,i]]=b[9]=1,表示第i位数字第1次是9} j:=2; {循环长度的初值=2}whiLe true do beginmuLti(a[j],a[j-1],ss); {ss=n,a[j-1]=a[1]=n,自乘}if b[a[j,i]]=0{a:array[1..11,0..100] of longint,共0..9,乘11次一定会出现重复数字,但不能确定是第1次的值,如果第j次乘幂后,这个数字是首次出现(多数情况是这样), b[a[j,i]]=b[任何1个没有出现的数字]=j, 表示第i位数字第j次出现的}then begin b[a[j,i]]:=j; inc(j); endeLse beginsc:=ss; ij:=b[a[j,i]];if ij<>1{某一位数值出现了循环,但不是初始值,则这个循环节不是所求的,中断整个程序,一般不会出现在个位}then begin writeLn(-1); cLose(input); cLose(output); haLt;end;circLe[i]:=j-1;{循环长度=幂次方-1，并记录在circle数组里}for ij:=2 to j-1 do muLti(ss,sc,ss); {改变了SS,使SS是初始的(j-1)-2+1次幂}j:=2; break; {退出whiLe循环，检测下1位的循环长度}end;end;end;fiLLchar(tot,sizeof(tot),0); tot[0]:=1;for i:=1 to k do muLt(tot,circLe[i-1]);for i:=k-1 downto 0 do if tot[i]>0 then break;for j:=i downto 0 do write(tot[j]);cLose(input); cLose(output);end.。
