Vijos p1032 循环[递推找思路]

　　众所周知，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位都相同。

 

【输入】

 

输入只有一行，包含两个整数n（1 <= n < 10^100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。

 

【输出】

 

输出包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。

 

【样例输入】

 

32 2

 

【样例输出】

 

4

【题解】

 

此题为NOIP原题，难度和复杂度较大

 

首先，我们看数据范围10^100，就知道数据有多阴险了（一股寒意袭来）~(≧▽≦)/

 

然而真正需要计算的部分就是后k位了，我们可以从尾来分析→既后1位，后2位，后3位，后4位……后k位，递推去找

 

假使输入数据位198123 4

 

①截取后4位8123，只需对8123做处理（输入时需注意，首先输入一个字符串，分割后存入数组）

 

②首先取最后一位3，寻找循环节（此时，用布尔数组判断是否存在循环，若不存在，直接输出-1)

 

   3,9,7,1,*3，循环长度为4

 

③此时，取后两位23：(23^4) mod 100=41 此时，23需每次乘以41，可保证最后一位不变

 

 23*41^n的循环节为43 63 83 03 23 循环节长度为5，此时，循环总长度位4*5=20

 

④通第3步操作，取后三位123：（123^20) mod 1000=201

 

123*201^n的循环节为723 323 923 523 123 循环节长度为5，此时总长度位20*5=100

 

⑤还是一样，取后四位8123：(8123^100) mod 10000=6001

 

8123*6001^n的循环节位6123 4123 2123 0123 8123 循环节长度为5，此时总长度位100*5=500

 

答案就出来了

 

做题时需注意高精的运用和字符串处理

 

还需注意，每次的（n^m) mod 10^a的结果需要代到下一次中，否则会超时！（计算时，须整个后k位都要乘）

 

 

附PASCAL代码

 

 

type use=array[1..1000] of integer;  
var n:string;  
    meen,realk:integer;  
    num1,ans,need:use;  
  
procedure init;  
 var inite,k:string;  
     space,error,for1:integer;  
 begin  
  readln(inite);  
  space:=pos(' ',inite);  
  n:=copy(inite,1,space-1);  
  k:=inite; delete(k,1,space);  
  val(k,realk,error);  
  if length(n)>=for1 then delete(n,1,length(n)-realk);  
  for for1:=realk downto 1 do if length(n)>=for1 then  
   num1[realk-for1+1]:=ord(n[for1])-48 else num1[realk-for1+1]:=0;  
 end;  
  
procedure mult(var a:use;b:use;k1,k2:integer);  
 var for1,for2,x,y,m:integer;  
     c:array[1..100] of integer;  
 begin  
  fillchar(c,Sizeof(c),0);  
  if k1>k2 then m:=k1 else m:=k2;  
  for for1:=1 to k1 do  
   for for2:=1 to k2 do begin  
    x:=a[for1]*b[for2];  
    y:=c[for1+for2-1];  
    if for1+for2-1<=m then c[for1+for2-1]:=(x+y) mod 10;  
    if for1+for2<=m then c[for1+for2]:=c[for1+for2]+(x+y) div 10;  
   end;  
  for for1:=1 to m do a[for1]:=c[for1];  
 end;  
  
procedure TheWrongWay;  
 begin  
  writeln(-1);  
  readln;  
  halt;  
 end;  
  
procedure working;  
 var for1,for2,for3,box,new:integer;  
     num2,num3,rp:use;  
     find:array[0..9] of boolean;  
     Yes:boolean;  
 begin  
  fillchar(need,Sizeof(need),0);  
  for for1:=1 to realk do begin  
   if for1=1 then begin  
    ans[1]:=1;  
    new:=1;  
    fillchar(num3,Sizeof(num3),0);  
    for for2:=1 to realk do num3[for2]:=num1[for2];  
   end;  
   fillchar(num2,Sizeof(num2),0);  
   for for2:=1 to realk do num2[for2]:=num3[for2];  
   if for1>1 then for for2:=1 to (need[for1-1])-1 do mult(num3,num2,realk,realk);  
   for for2:=1 to for1 do num2[for2]:=num1[for2];  
   new:=0; fillchar(find,Sizeof(find),false);  
   box:=num2[for1];find[box]:=true;Yes:=false;  
   repeat  
    inc(new);  
    mult(num2,num3,for1,for1);  
    if not find[num2[for1]] then find[num2[for1]]:=true else begin  
     if num2[for1]<>box then TheWrongWay else Yes:=true;  
    end;  
   until Yes;  
   need[for1]:=new;  
   fillchar(rp,Sizeof(rp),0);  
   if new=10 then begin  
    rp[2]:=1;  
    rp[1]:=0;  
   end else rp[1]:=new;  
   mult(ans,rp,100,2);  
  end;  
 end;  
  
procedure print;  
 var for1,for2:integer;  
 begin  
  for1:=100;  
  while ans[for1]=0 do dec(for1);  
  for for2:=for1 downto 1 do write(ans[for2]);  
  writeln;  
  readln;  
 end;  
  
begin  
 init;  
 working;  
 print;  
end.