P1050 循环

_Life_ · 2021-06-29 10:30:30 · 题解

题意

给定两整数 n,k，求 n 的正整数次幂的最后 k 位的循环长度，若循环不存在输出 -1。

题解

这篇题解是对最高赞题解的补充与说明

在看最高赞题解的时候，因为没有放上计算过程，我对着题解手玩了好久才弄明白，所以就有了这篇附上计算过程的题解。

手玩数据 198123 4，因为要求只取后 4 位，所以将其截取成 8123。

我们逐位进行处理：

• 先处理最后一位的循环节：最后一位是 3，循环节长度为 4。所以后两位的循环节长度一定为 4 的倍数，为了加快计算，我们可以将乘数变为 8123^4 ，取后 4 位变成 0641。
• 再处理后两位：后两位是 23 ，在乘了 5 次 0641 后出现了循环，循环节长度为 4*5=20。同样为了加快计算，乘数变为 8123^20=0641^5，取后 4 位变成 9201。之后就按照这样的方法处理即可。
• 后三位：后三位是 123 ，乘了 5 次 9201 后出现循环，循环节长度为 20*5=100 ，乘数变为 9201^5%(10^4)=6001
• 后四位：后四位是 8123 ，乘了 5 次 6001 后出现循环，循环节长度为 100*5=500，500 就是最终的答案。

记得判断无解的情况：如果在处理某一位时，乘了乘数 10 次，还是没有出现循环，无解。

8123               1
8123*8123=65983129 2
3129*8123=25416867 3
6867*8123=55780641 4
0641*8123=05206843 #
8123^4=4353773312630641

8123               1
8123*0641=05206843 2
6843*0641=04386363 3
6363*0641=04078683 4
8683*0641=05565803 5
5803*0641=03719723 #
0641^5=108215668739201

8123               1
8123*9201=74739723 2
9723*9201=89461323 3
1323*9201=12172923 4
2923*9201=26894523 5
4523*9201=41616123 #
9201^5=65943979755726446001

8123               1
8123*6001=48746123 2
6123*6001=36744123 3
4123*6001=24742123 4
2123*6001=12740123 5
0123*6001=00738123 #

ans=4*5*5*5=500

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int k;
char str[205];
struct bignum
{
    int x[205];
    bignum(){memset(x,0,sizeof(x));}
}n,tmp,mul,ans;
bignum operator *(bignum a,bignum b)//特化过的高精乘 只取后k位
{
    bignum ans;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            ans.x[i+j]+=a.x[i]*b.x[j];
    for(int i=0;i<k;i++)ans.x[i+1]+=ans.x[i]/10,ans.x[i]%=10;
    for(int i=k;i<205;i++)ans.x[i]=0;
    return ans;
}
bignum operator *(bignum a,int b)//这个高精乘低精是ans专用的233
{
    for(int i=0;i<=200;i++)a.x[i]*=b;
    for(int i=0;i<=200;i++)a.x[i+1]+=a.x[i]/10,a.x[i]%=10;
    return a;
}
int main()
{
    scanf("%s %d",str,&k);
    ans.x[0]=1;
    int len=strlen(str);
    for(int i=0;i<k;i++)
        n.x[i]=str[len-i-1]-'0';
    mul=n;
    for(int i=0;i<k;i++)
    {
        bignum tmp=n;
        int j=1,flag=1;
        for(j=1;j<=10;j++)
        {
            tmp=tmp*mul;
            if(tmp.x[i]==n.x[i])
            {
                ans=ans*j;
                flag=0;
                break;
            }
        }
        if(flag)
            return puts("-1"),0;
        tmp=mul;
        for(int k=1;k<j;k++)
            mul=mul*tmp;
    }
    len=200;
    while(ans.x[len]==0&&len>=1)len--;
    for(;len>=0;len--)putchar(ans.x[len]+'0');
}