Vijos p1032 循环【递推找思路】

文章转自：http://luoxinhe168.blog.163.com/blog/static/331283882011685733172/

【题目描述】

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
　　众所周知，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.