A41064. 循环
填空题
困难
知识点
题目描述
循环
题目描述
乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，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（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。
输出格式
输出一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。
样例输入
32 2
样例输出
4
参考答案
#include<stdio.h>
#include<string.h>
int xx(char *a,char *b,char *c)
{
int i,j,t=0,k;
for(i=0;b[i]!=NULL&&i<100;i++)
{
for(j=0;a[j]!=NULL&&j<100;j++)
{
if(i+j<100)
{
if(c[j+i]==NULL)
{
c[j+i]='0';
if(j+i+1<=100)
c[j+i+1]=NULL;
}
t=(c[j+i]-'0')+(a[j]-'0')*(b[i]-'0');
c[j+i]=t%10+'0';
t=t/10;
k=j+i+1;
while(t!=0&&k<100)
{
if(c[k]==NULL)
{
c[k]='0';
c[k+1]=NULL;
}
t=t+(c[k]-'0');
c[k]=t%10+'0';
t=t/10;
k++;
}
}
}
}
return 0;
}
int add(char *m,char *nm)
{
int i,t=0,k;
for(i=0;i<200;i++)
{
if(m[i]==NULL&&nm[i]==NULL)
break;
else if(m[i]==NULL)
{
m[i]='0';
m[i+1]=NULL;
}
else if(nm[i]==NULL)
{
nm[i]='0';
nm[i+1]=NULL;
}
t=(m[i]-'0')+(nm[i]-'0');
m[i]=t%10+'0';
t=t/10;
k=i;
while(t!=0)
{
k++;
if(m[k]==NULL)
{
m[k]='0';
m[k+1]=NULL;
}
t=m[k]-'0'+t;
m[k]=t%10+'0';
t=t/10;
}
}
}
int main()
{
// long int bug=0;
int a,b,i,j,p=0,end=0,w=0;
char n[102],t[102],c[102],tempm[102],tempnm[102],mast[102],m[200],nm[200];
char check[200];
scanf("%s",check); //找了好久终于找到了错的地方，，，原来输入问题。
scanf("%d",&b);
j=0;
for(i=(int)strlen(check)-1;i>=0&&j<=100;i--)
{
n[j]=check[i];
j++;
}
n[j]=NULL;
//这里是原本的整型输入
// scanf("%d %d",&a,&b);
m[0]='0';
m[1]=NULL;
nm[0]='1';
nm[1]=NULL;
/*
for(i=0;i<b;i++)
{
n[i]=a%10+'0';
a=a/10;
}
n[i]=NULL;
*/
strcpy(mast,n);
strcpy(t,n);
tempm[0]='1';
tempm[1]=NULL;
for(i=1;i<=b;i++)
{
tempnm[0]=NULL;
c[0]=NULL;
xx(n,t,c);
xx(tempm,t,tempnm);
tempnm[b+1]=NULL;
c[b]=NULL;
add(m,nm);
p=0;
for(j=w;j<b;j++)
{
if(c[j]!=mast[j])
{
i=w;
break;
}
else
{
p=1;
w++;
}
}
if(p==1)
{
strcpy(nm,m);
if(w==b)
{
for(i=(int)strlen(m)-1;i>=0;i--)
{
printf("%c",m[i]);
// bug=bug*10+(m[i]-'0');
}
// printf("%ld",bug);
return 0;
}
strcpy(t,tempnm);
}
strcpy(tempm,tempnm);
strcpy(n,c);
end++;
if(end==100000)
{
break;
}
}
printf("-1");
return 0;
}
上一题
下一题