题目描述

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。

众所周知，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和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。

输出描述:

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

示例1

输入
32 2
输出
4

备注:

对于30%的数据，
对于全部的数据，。

解答

一开始我的思路就已经有点沾正解的边了，一开始我是认为对于最终的结果SOLVE(N,K)，这个数一定是N的最后一位的循环节的倍数，比如说：SOLVE(1234567,7)一定是7的循环节，也就是4的倍数。然后就可以每进行一次乘法，不考虑精度的话，本以为这样就能得出30%的答案了，但是只得了2个点。 
这里我们记X的循环节为FUNC(X)，经过半个下午的思考，发现其实自己只需要把刚才的思路再拓展一下就好了。 
比如说以SOLVE(223,3)为例，此时T=FUNC(3)=4模拟一下就是 




先让它的倍增单位变为，也就是每次都乘上441，然后就能保证个位每次都是3，记录循环节4，解释一下就是： 





这个时候发现，223的十位为2，823的十位也为2，这样每次倍增单位就变成了，然后就能保证十位每次都是2，个位每次都是3。记录循环 





这个时候发现，223的百位为2，求出的223的百位也为2，这时得到的数已经到了K位了。然后就能保证百位每次都是2，十位每次都是2，个位每次都是3。记录循环。 
然后输出即可。 
通过模拟可能思路就比较明晰了。 
过程中要用到一个高精乘高精和一个高精乘低精，然后个人认为没必要为了省这点时间去打长长的高精度快速幂。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<set>
using namespace std;
int a[201],k,i,j,t[201];
int shl[10]={1,1,4,4,2,1,1,4,4,2};
string s;
int last[201];
int n[201],ans[201],aans[201],now[201];
int r()
{
    int ans=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ans*=10;
        ans+=ch-'0';
        ch=getchar();
    }
    return ans*f;
}

void multiply(int x[],int y[],int z[])
{
    int up=0;//进位 
    for(int ii=1;ii<=k;ii++)
    {
    for(j=1;j<=k;j++)
    {
        z[ii+j-1]+=(x[j]*y[ii]+up)%10;
        up=(x[j]*y[ii]+up)/10;
    }
    up=0;}

    for(int ii=1;ii<=k;ii++)
    {
    z[ii+1]+=z[ii]/10;
    z[ii]%=10;
    }
}

void multiply1(int x[],int yy,int z[])
{
    int up=0;//进位 
    for(int ii=1;ii<=k;ii++)
    {
    z[ii]=(x[ii]*yy+up)%10;
    up=(x[ii]*yy+up)/10;
    }
}

int main()
{
//  freopen("circle.in","r",stdin);
//  freopen("circle.out","w",stdout);
    cin>>s;
    k=r();

    int temp=0,len=s.size();
    for(i=len-1;i>=len-k;i--)
    n[++temp]=s[i]-'0';
    for(i=1;i<=k;i++)
    ans[i]=n[i];

    for(i=1;i<shl[n[1]];i++)
    {
        memset(aans,0,sizeof(aans));
        multiply(ans,n,aans);
        for(j=1;j<=k;j++)
        {
            ans[j]=aans[j];
        }
    }

    t[1]=shl[n[1]];

    for(j=1;j<=k;j++)
    now[j]=ans[j];


    int pos=2;
    while(pos<=k)
    {
    for(j=1;j<=k;j++)
    ans[j]=n[j],last[j]=now[j];
    temp=0;
    while(temp<11)
    {
        temp++;

        memset(aans,0,sizeof(aans));
        multiply(ans,now,aans);
        for(j=1;j<=k;j++)
        ans[j]=aans[j];

        if(ans[pos]==n[pos])
        break;

        memset(aans,0,sizeof(aans));
        multiply(last,now,aans);
        for(j=1;j<=k;j++)
        last[j]=aans[j];
    }
    if(temp>=11)
    {
        cout<<-1;return 0;
    }
    for(j=1;j<=k;j++)
    now[j]=last[j];

    memset(aans,0,sizeof(aans));
    multiply1(t,temp,aans);
    for(j=1;j<=100;j++)
    t[j]=aans[j];

    pos++;
    }
    int kk=0;
    for(i=100;i>=1;i--)
    {
    if(t[i])
    kk=1;
    if(kk)
    cout<<t[i];
    }

    return 0;
}


来源：Stockholm_Sun