题意

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

$1\le n\le 10^{100},1\le k \le 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=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');
}

转载自 https://www.luogu.com.cn/blog/_post/343347