P1050 [NOIP2005 普及组] 循环

题目描述

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

众所周知，22 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6…2,4,8,6,2,4,8,6… 我们说 22 的正整数次幂最后一位的循环长度是 44（实际上 44 的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：

数字循环循环长度22,4,8,6433,9,7,1444,6255166177,9,3,1488,4,2,6499,12数字23456789​循环2,4,8,63,9,7,14,6567,9,3,18,4,2,69,1​循环长度44211442​​

这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数 �n 的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？

注意：

1. 如果 �n 的某个正整数次幂的位数不足 �k，那么不足的高位看做是 00。
2. 如果循环长度是 �L，那么说明对于任意的正整数 �a，�n 的 �a 次幂和 �+�a+L 次幂的最后 �k 位都相同。

输入格式

共一行，包含 22 个整数 �n 和 �k。�n 和 �k 之间用一个空格隔开，表示要求 �n 的正整数次幂的最后 �k 位的循环长度。

输出格式

一个整数，表示循环长度。如果循环不存在，输出 −1−1。

输入输出样例

输入 #1复制

32 2

输出 #1复制

4

说明/提示

【数据范围】

对于 30%30% 的数据，满足 �≤4k≤4；
对于100%100% 的数据，满足 1≤�<101001≤n<10100，1≤�≤1001≤k≤100。

【题目来源】

NOIP 2005 普及组第四题

题意

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

1≤�≤10100,1≤�≤1001≤n≤10100,1≤k≤100

题解

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

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

手玩数据 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=43537733126306418123               1
8123*0641=05206843 2
6843*0641=04386363 3
6363*0641=04078683 4
8683*0641=05565803 5
5803*0641=03719723 #
0641^5=1082156687392018123               1
8123*9201=74739723 2
9723*9201=89461323 3
1323*9201=12172923 4
2923*9201=26894523 5
4523*9201=41616123 #
9201^5=659439797557264460018123               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');
}