循环 （C++代码）

解题思路:





注意事项:





参考代码:

5种代码

考察高精，累乘。

循环条件：原数*累乘器=原数。

此时：原数*累乘器=原数。

即乘n个累乘器，已匹配的位数不改变。

1位位地匹配，如果某一位出现11个数字，则必定没有循环。

注意每一位匹配后，累乘器要更新。

#include<cstdio>#include<cstring>int ans[101];int a[101],n=0,k;int i,j,rec[101],newn[101];char ch[101];bool judge(int k) //计算是否循环 {    int s[102];    memset(s,0,sizeof(s));    for (int i=1; i<=n; i++)      for (int j=1; j<=newn[0]; j++)        if (i+j-1 > k) break;        else
       {
          s[i+j-1]+=a[i]*newn[j];
          s[i+j]+=s[i+j-1]/10;
          s[i+j-1]%=10;
       }    if (s[k] == a[k]) return 1;    return 0;
}void mul() //累乘 {    int s[102];    memset(s,0,sizeof(s));    for (int i=1; i<=rec[0]; i++)      for (int j=1; j<=newn[0]; j++)        if (i+j-1 <= n)
       {
          s[i+j-1]+=rec[i]*newn[j];
          s[i+j]+=s[i+j-1]/10;
          s[i+j-1]%=10;
       }    if (rec[0]+newn[0]-1 >= n) s[0]=n;    else if (s[rec[0]+newn[0]] > 0) s[0]=rec[0]+newn[0];    else s[0]=rec[0]+newn[0]-1;    for (int i=0; i<=s[0]; i++)
     newn[i] = s[i];
}void calc(int x) //单精*高精 {    
   for (int i=1; i<=ans[0]; i++)
     ans[i]*=x;    for (int i=1; i<=ans[0]; i++)
   {
       ans[i+1]+=ans[i]/10;
       ans[i]%=10;
   }    while (ans[ans[0]+1] > 10)
   {
       ans[0]++;
       ans[ans[0]+1]+=ans[ans[0]]/10;
       ans[ans[0]]%=10;
   }    if (ans[ans[0]+1] > 0) ans[0]++;
}int main(){    scanf("%c",&ch[++n]);    while (ch[n] != ' ')      scanf("%c",&ch[++n]);    scanf("%d",&k);
   n--;    for (i=1; i<=n; i++)
     a[i]=ch[n+1-i]-'0';    if (n > k) n=k;    if (n < k)
   {      for (i=n+1; i<=k; i++)
       a[i] = 0;
     n = k;
   } //init
   for (i=1; i<=n; i++)
     rec[i]=a[i]; //last one 加数
   rec[0]=n;
   for (i=1; i<=n; i++)
     newn[i]=a[i];
   newn[0]=n; //rec^x (累乘器)
   ans[0]=1; ans[1]=1;    for (i=1; i<=k; i++)
   {        if (judge(i)) continue; //第i位相等
       else for (j=2; j<=11; j++)
       {
           mul(); //累乘器
           if (judge(i)) break;
       }        if (j > 11) //无解
       {            printf("-1");            return 0;
       }        
       calc(j); //ans=ans*j;
       for (j=newn[0]; j>=0; j--)
         rec[j]=newn[j];
   }    for (i=ans[0]; i>=1; i--)      printf("%d",ans[i]);    return 0;
}

评论

还没有评论

评论

此题为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位都要乘）

评论

还没有评论

评论

作者: zsj123 更新时间: 2016-11-12 21:55  在Ta的博客查看  1 

题解：

主要是应用高精度算法，加上一些优化算法

大家都知道要取数的后面的N位就要用数去除以10n。所以题目就容易解决了。首先输入SS为要乘的正整数和要求的位数，因为输入的是一个字符串，所以只有找空格来读入两个数。将要乘的数放入s1中，剩下的length(ss)-I位为要求的位数放入k中。又因为经过实验发现当k超过20时是不存在的，所以当k大于20时可以直接打印-1，但相反如果小于20，首先对输入的 k进行处理，可以算出用于取后k位的L来。然后进行循环用输入的s1乘以s1再取后k位，然后又把新得到的要乘的数乘以s1在取后k位……依次反复，当得到的数的后k位等于s1的后k位时结束，否则依然继续直到循环10000次。

标程：PASCAL

Program Circle;Type
 Arr=Array[1..101] Of Integer;Var
 i,j,p,k,code,L,num,tp:Integer;
 s: String;
 a,aa,time,b,temp:Arr;//高精度乘法Procedure Mutiply(a, b:Arr;Var c:Arr;t:Integer);Var
 i, j: Integer;Begin
 FillChar(c, SizeOf(c), 0);  For i:=1 To t Do
   For j:=1 To t-i+1 Do
   Begin
     c[i+j-1]:=a[i]*b[j]+c[i+j-1];
     c[i+j]:=c[i+j]+c[i+j-1] Div 10;
     c[i+j-1]:=c[i+j-1] Mod 10;    End;End;//高精度乘法，计算总次数，L表示次数的长度Procedure Mutiply(a:Arr;b:Integer;Var c:Arr;Var L:Integer);Var
 i: Integer;Begin
 FillChar(c,SizeOf(c),0);  For i:=1 To L Do
 Begin//这里是乘，因为如果个位需要5次，十位需要5次，那么肯定需要25次才可以满足个位和十位的要求c[i]:=c[i]+a[i]*b;
   c[i+1]:=c[i] Div 10;
   c[i]:=c[i] Mod 10;  End;  If c[L+1]<>0 Then
   Inc(L);End;Begin
 //重定位标准输入和标准输出设备
 Assign(Input, 'circle.in');
 Assign(Output, 'circle.out');
 ReSet(Input);
 ReWrite(Output);
 ReadLn(s);  //分两部分截取s，和循环位数K
 Val(Copy(s, Pos(' ', s)+1, Length(s)-Pos(' ', s)), k, code);
 Delete(s, Pos(' ', s), Length(s)-Pos(' ', s)+1);//将S倒转转化为数值存在数值类型的数组中以便于计算
 For i:=1 To Length(s) Do
   Val(s[i], a[Length(s)-i+1], code);
 aa:=a;//初始化次数数组
 FillChar(time, SizeOf(time), 0);
 time[1] := 1;
 L := 1;//开始计算
 For i:=1 To k Do
 Begin
   //从一位开始对比，直到K位，b为比较的初始数组
   For j:=1 To i Do
     b[j] := aa[j];
   tp := b[i];//TP为比较的位的值
   num := 0;    Repeat
     Mutiply(b, a, b, i);
     Inc(num);    Until (num > 10) Or (b[i] = tp);//超过10次则代表就是无法满足循环条件了，因为只有10个数0..9
   If (b[i] <> tp) Then Begin
     Write(-1);
     Close(Input);
     Close(Output);
     Halt(0);    End;//根据需要几次才能满足，变化基础的乘因子a
   temp := a;    For j:=1 To num-1 Do
     Mutiply(a, temp, a, k);
   Mutiply(time, num, time, L);  End;//反输出time，表示最终需要次数
 For i:=L DownTo 1 Do Write(time[i]);
 Close(Input);
 Close(Output);End.

以上就是对第四题的解释。其中应用了几个巧妙的方法提高了运算的效率，如其中最突出的是基础因子法的使用以及计算总次数时的高精度乘法使用。 {代码似乎有毒！！！}

评论

wxk01
太棒了！

叶任成。
good

评论

作者: 2016gdgzoi471 更新时间: 2017-09-29 22:49  在Ta的博客查看  0 

很显然要使用高精度。我们首先考虑一种暴力：累乘直到出现循环。这样时间复杂度太高，显然需要一些优化。可以想到一种思路，即从低位到高位一位一位地匹配，不断地乘因数直到这一位与开始时相同。这里有一个关键优化：每次乘的因数是上一位匹配后累乘的积，这样前面已经匹配的几位就不会变化，避免了大量不必要的重复。注意，如果某一位乘的次数大于10，即这一位0到9取遍了仍没有循环，说明这一位不可能出现循环，直接输出-1，否则答案就乘上这一位匹配所乘的总次数。注意，答案很大，所以答案也要使用高精度。时间复杂度O(K^3)。因为每一位可能会乘1~10次，所以算上常数实际时间复杂度会更高一些。

评论

还没有评论

评论

一般认为，某数的的N次方的后K位，与该数的后K位有关，K位之前不影响

就是12、122、的N次方的最后1位数，只与12中的2、122中的2有关

因此对整数N，求其最后K位的循环时，只要考虑N的后K位。

又认为，当尾数中第二次出现某值，则必从该值后即开始循环

以下代码用VBS实现，在WINDOWS系统中把代码复制进空文本文件，保存改后缀名为VBS，可以双击运行

'=========代码开始=========

'撇号开头的行是注释

'仅用于实现.限于VBS的性能，在验证很大的K时耗时极多

'n,k的输入值，没有做输入，可以手工修改

'j是寻找循环尾数的旗标

'ws是存储尾数的以逗号分隔的字符串、并可分解为尾数数组

'ts是存储某次幂尾数的字符串

n = 2k = 1j = 1ws = ""ts = ""

'制造一个长度为K的字符串，全部由0构成，用于补齐 for i = 1 to k

w = w & "0"

next

'初始化时，也就是幂次为1时

n = cutw (n)

ws= addw (n)

'm专门用于乘方计算

m = ndo until j = 0
  ts = ""
  m = cutw (m*n)
  ts = addw (m)

'判断尾数ts是否已在ws中存在 if Instr (ws,ts) then

ws = ws & "," & ts  

'存在，设置j值以退出循环

   j = 0else
  ws = ws & "," & ts
  j = j + 1end if

loop

'将所有尾数字符串分解为数组

ws = split (ws,",")

for i = 0 to Ubound (ws)

'查找循环开始的尾数，重复出现的尾数正位于数组最后

if ws (i) = ts then

'我的输出方式

MsgBox "尾数有循环，从第" & i+1 & "次方开始，最早于第" & Ubound (ws) +1 & "次方出现重复，" & "最小循环长度为" & Ubound (ws) - i

Wscript.Quit

end if

next

'函数cutw用于截断获得K位尾数

function cutw (p)   if Len (p) > k then
     cutw = right (p,k)   else
     cutw = p   end ifend function

'函数addw用于补齐K位尾数

function addw (q)   if Len (q) < k then
     addw = Right (w & q,k)   else
     addw = cutw (q)   end ifend function'=========代码结束=========