circle解题报告.doc

Circle解题报告
众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
1．如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。
2．如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a+L次幂的最后k位都相同。

那么，举例来说：
125，625，78125，9765625。。。。。
125后三位的循环就是2

基本思路就是：
首先在数n^1,n^2,n^3...求出最后一位的循环长度l1,无解则输出-1
接着在数n^1,n^(l1+1),n^(2*l1+1),..求出最后两位的循环长度l2,无解则输出-1
然后在数n^1,n^(l2+1),n^(2*l2+1),...求出最后三位的循环长度l3,无解则输出-1
最后答案l=l1*l2*l3..lk

var
s:ansistring;
a,b,a1:array[1..200]oflongint;
i,j,k,linsum,len:longint;
sum:array[0..200]oflongint;
functionpan(i:longint):boolean;判断函数
varj:longint;
begin
forj:=1toido
ifa[j]<>b[j]thenexit(false);
exit(true);
end;

procedurecalc;高精度乘法1
var
i,j:longint;
a1:array[1..200]oflongint;
begin
fillchar(a1,sizeof(a1),0);
fori:=1tokdo
forj:=1tokdo
a1[i+j-1]:=a1[i+j-1]+a[i]*b[j];
fori:=1tok-1do
ifa1[i]>9then
begin
a1[i+1]:=a1[i+1]+a1[i]div10;
a1[i]:=a1[i]mod10;
end;
a1[k]:=a1[k]mod10;
a:=a1;
end;

procedureclac(i:longint);高精度2
varj:longint;
begin
forj:=1to200do
sum[j]:=sum[j]*i;
forj:=1to200do
begin
sum[j+1]:=sum[j+1]+sum[j]div10;
sum[j]:=sum[j]mod10;
end;
end;

begin
assign(input,'circle.in');
assign(output,'circle.ans');
reset(input);
rewrite(output);
fillchar(sum,sizeof(sum),0);
readln(s);
i:=1;
while(s[i]<>'')AND(i<=length(s))do
inc(i);
k:=0;
j:=i+1;
whilej<=length(s)do
begin
k:=k*10+ord(s[j])-ord('0');
inc(j);
end;
s:=copy(s,1,i-1);
fori:=1tokdo
iflength(s)-i+1>=0thena[i]:=ord(s[length(s)-i+1])-ord('0');
sum[1]:=1;
a1:=a;
fori:=1tokdo计算每一位的循环次数
begin
b:=a1;
a:=b;
linsum:=1;每一位的循环次数计数器
calc;
while((not(pan(i)))and(linsum<=100))do计算循环
begin
a1:=a;
calc;
inc(linsum);
end;
iflinsum>100then判是否有循环
begin
writeln(-1);
close(input);
close(output);
halt;
end;
linsum:=linsum;

clac(linsum);
end;
len:=200;
whilesum[len]=0dodec(len);输出不解释
fori:=lendownto1do
write(sum[i]);
writeln;
close(input);
close(output);
end.

测试点12345时间0.02s0.01s0.00s0.14s0.04s测试点678910时间0.17s0.24s0.18s0.23s0.30s总结：本题主要是应用递推关系，大大简化算法的时间复杂度。死做肯定会爆。本题侧重的算法在于递推与高精度。