【问题描述】
中华上下五千年简介乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，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(1n< 10100)和k(1k100)，n和wr842nk之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
【输出文件】
输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。
【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据，k4；对于全部的数据，k00。
| 循环 | 循环长度 |
2 | 2、4、8、6 | 4 |
3 | 3、9、7、1 | 4 |
4 | 4、6 | 2 |
5 | 5 | 1 |
6 | 6 | 1 |
7 | 7、9、3、1 | 4 |
8 | 8、4、2、6 | 4 |
9 | 9、1 | 2 |
| | |
从个位开始判断:几轮循环后,如果出现1(个位数字的第1次),计算循环长度j,连续自乘幂j次,转(2)；
如果没有出现1,出现了其它数字,则循环节不存在,输出-1后结束。
(1) 依次判断十位……。
(2) 每个数字的循环长度纪录在circle数组。
(3) 如果能计算至最高位,则circle数组的每1个元素连乘就是要求的n的正整数次幂的最后k位的循环长度。
[例] n=32
32 | 乘幂 | 积 | 十位 | 个位 | j |
| 1 | 32 | 3 | 2 | |
| 2 | 1024 | 2 | 4 | 2 |
| 3 | 32768 | 6物理学原理 | 8 | 3 |
| 4 | 1048576 | 7 | 6 | 4 |
| 5 | 33554432 | 3 | 2 | 5 |
| | | | | |
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=4
const max=100;
type hint=ax]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:ax]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;
begin
fiLLchar(a,sizeof(a),0);
for i:=0 to k-1 do
for j:=0 to k-1 do
if i+j<=k-1 then inc(a[i+j],b[i]*c[j]);
e:=0;
for i:=0 to k-1 do begin
a[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;
begin
for i:=0 to a[max] do a[i]:=a[i]*b;
e:=0;
for i:=0 to a[max]+1 do begin
a[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;
begin
assign(input,'circLe.in'); ret(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 do
begin {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 begin
muLti(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); end
eL begin
sc:=ss; ij:=b[a[j,i]];
if ij<>1{某一位数值出现了循环,但不是初始值,则这个循环节不是所求的,中断整个程序,一般不会出现在个位}
then begin writeLn(-1); cLo(input); cLo(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]);
cLo(input); cLo(output);
end.
