玄学做法

按照题目模拟，寻找循环，可以过小数据。

时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
int main()
{
	LL n,k;
	cin>>n>>k;
	LL p=1;
	set<LL> h; //集合 
	for(int i=1;i<=k;i++) //截取k位 
	{
		p=p*10;
	}
	n=n%p;
	LL first=n; //第一个值
	LL s=n;
	for(int i=2;i<=100000;i++) //累乘次数 
	{
	    s=s*n%p;
		if(s==first) //找到循环 
		{
			cout<<i-1;
			return 0;
		}
	}
	cout<<-1; //找不到 
    return 0;
}

递推写法

基础理论

1.$k+1$位循环节一定是$k$位置循环节的倍数

2.由抽屉原理可得由k位计算到k+1位的时候，最多计算11次.

时间复杂度

总共需要递推 $k$位，每次递推时最多需要枚举$10$项,，所以时间复杂度是 $Ok^3$

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int nums[N],k;
void mul(int c[],int a[],int b[])
{
    int temp[N]={};
    for(int i=0;i<k;i++) //高精度模板 
    {
        for(int j=0;j<k;j++)
        {
            if(i+j<k)
            {   
                temp[i+j]+=a[i]*b[j];
            }
        }
    }
    for(int i=0;i<k;i++) //高精度处理进位模板 
    {
        temp[i+1]+=temp[i]/10;
        temp[i]%=10;
    }
    memcpy(c,temp,sizeof temp);
}
bool check()
{
    int t[N]={1},q[N];
    memcpy(q,nums,sizeof q);//最开始的循环节就是输入的这个数的个位
    for(int i=1;i<=k;i++)
    {
        int p[N];//表示当前循环节累乘的结果
        bool st[N]={}; //一个清空的状态数组
        memcpy(p,q,sizeof p); //初始化累乘结果 
        int j; //乘的次数 
        for(j=1;j<=10;j++) //最多乘10次 
        {
            mul(p,p,q);//累乘
            if(p[i-1]==q[i-1]) break; //找到循环节 
            if(st[p[i-1]]==1) break; //找不到(中途出现的数字)
            st[p[i-1]]=1; 
        }   
        if(p[i-1]!=q[i-1]) //找不到循环节 
        {
            return false;
        }
        int o[N]={j}; //得到新的循环节需要乘几次 
        mul(t,t,o); //更新循环节长度 
        memcpy(p,q,sizeof p); //初始化 
        for(int k=1;k<j;k++) //计算循环节 
        {
            mul(p,p,q);
        }
        //更新循环节
        memcpy(q,p,sizeof p); 
    } 
    //说明一定是有循环节，且t为循环节的长度
    int lenc=N-1;
    while(lenc>0&&t[lenc]==0) lenc--;//去除前导0
    for(int i=lenc;i>=0;i--)
    {
        cout<<t[i];
    }
    return true; //表示当前是找到了循环节的 
}
int main()
{
    string s;
    cin>>s>>k;
    for(int i=0,j=s.size()-1;j>=0;i++,j--)
    {
        nums[i]=s[j]-'0';
    }
    if(!check()) cout<<-1;
    return 0;
}