首页 > 代码库 > 2005循环
2005循环
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
循环
循环长度
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
这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？
注意：
1．如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2．如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a+L次幂的最后k位都相同。
输入只有一行，包含两个整数n（1<=n<10100）和k（1<=k<=100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
输出包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。
32 2
4
【数据规模】
对于30%的数据，k<=4；
对于全部的数据，k<=100。
题解：
数论+高精度。
我们只需要计算后k位，而且我们可以从1位1位分析下去。我们就当样例来算一下：先求出最后一位2需要几次才能循环，求出答案4；在求32，后面的位数都相同，至少要32（4）的两位，得76（这一点我们可以在a数组上乘，会方便很多）。我们再让32每次*76，求出1。最后用4*1求得答案=4。
type ar=array[0..1001]of longint;
var i,j,s,k:longint;
n:ansistring;
a,b,ans:ar;
procedure cheng1(var a:ar;b:ar);
var i,j:longint;
c:ar;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to a[0]-i+1 do
begin
c[i+j-1]:=c[i+j-1]+a[i]*b[j];
c[i+j]:=c[i+j]+c[i+j-1]div 10;
c[i+j-1]:=c[i+j-1]mod 10;
end;
c[0]:=b[0];
a:=c;
end;
procedure cheng2(var a:ar;b:longint);
var i:longint;
c:ar;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
begin
c[i]:=a[i]*b+c[i];
c[i+1]:=c[i] div 10;
c[i]:=c[i] mod 10;
end;
c[0]:=a[0];
while c[c[0]+1]>0 do
begin
inc(c[0]);
c[c[0]+1]:=c[c[0]] div 10;
c[c[0]]:=c[c[0]]mod 10;
end;
a:=c;
end;
begin
readln(n);
val(copy(n,pos(‘ ‘,n)+1,length(n)),k);
delete(n,pos(‘ ‘,n),length(n));
inc(ans[0]);
inc(ans[1]);
a[0]:=length(n);
for i:=1 to a[0] do a[a[0]-i+1]:=ord(n[i])-48;
for i:=1 to k do
begin
for j:=1 to i do b[j]:=a[j];
b[0]:=i;
s:=1;
cheng1(b,a);
while (s<=10)and(b[i]<>a[i]) do
begin
cheng1(b,a);
inc(s);
end;
if b[i]<>a[i] then
begin
write(‘-1‘);
exit;
end;
b:=a;
for j:=1 to s-1 do cheng1(a,b);
cheng2(ans,s);
end;
for i:=ans[0] downto 1 do write(ans[i]);
end.
2005循环