循环

【问题描述】

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。
众所周知，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位都相同。

【输入文件】

输入文件circle.in只有一行，包含两个整数n（1 <= n < 10^100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。

【输出文件】

输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。

【样例输入】

32 2

【样例输出】

4

【数据规模】

对于30%的数据，k <= 4；
对于全部的数据，k <= 100。


我好像连题目都没有看懂...

k<=4还是容易做的，k<=100要大整数了，而且如何存储是个问题，最坏情况下有10^100个100位大整数，根本不可能存下来。

能过掉那30%的测试点，大整数的比较麻烦

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/*#define DEBUG*/
int used[10000];
char str[1000];
int power10[]={1,10,100,1000,10000};
int main()
{
    int k,t,i,cnt,n,res,len;
    while(scanf(\"%s %d\",str,&k)){
        cnt=0;
        res=-1;
        memset(used,0,sizeof(used));
        len=strlen(str);
        n=0;
        for(i=1;i<=k && len-i>=0 ;i++){
            n+=(str[len-i]-'0')*power10[i-1];
        }
#ifdef DEBUG
        printf(\"n=%d\n\",n);
#endif
        t=n;
        used[t]=++cnt;
        while(1){
            t=t*n%power10[k];
#ifdef DEBUG
            printf(\"t=%d\n\",t);
#endif
            if(used[t]){
                res=++cnt-used[t];
                break;
            }
            else {
                used[t]=++cnt;
            }
        }
        assert(res!=-1);
        printf(\"%d\n\",res);
    }
}

对了顺便说下，根据鸽巢原理，不可能不存在循环

我这里有一段C++的代码，但真是很难看，他的编程风格简直可以参加国际C混乱代码大赛了。
可以帮我解析一下吗？

//循环
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int d;
char str[255];
void chen(char *a,char *b)
{
char *c;
int i,j,k;
int l,l2;
l = strlen(a);
l2 = strlen(b);
c = (char *)malloc(sizeof(char)*(l+l2+1));
for(i = 0; i < l+l2+1; i++)
c[i] = '0';
int jin = 0;
for(i = l2-1; i >= 0; i--)
{
for(j = l-1; j >= 0; j--)
{
int temp = (a[j]-48) * (b[i]-48) + jin;
jin = 0;
if(temp >= 10)
{
jin = temp / 10;
temp = temp % 10;
}
c[i+j+1] += temp;
for(k = i+j+1; k > 0; k--)
if((c[k]-48)>=10)
{
c[k-1] += 1;
c[k] = c[k]-10;
}
else
break;
}
if(jin)
{
c[i+j+1] += jin;
for(int k = i+j+1; k > 0; k--)
if((c[k]-48)>=10)
{
c[k-1] += 1;
c[k] = c[k]-10;
}
else
break;
jin = 0;
}
}
if(jin)
c[0]+=jin;
else if(c[0]=='0')
{
memcpy(c,c+1,sizeof(char)*(l+l2-1));
c[l+l2-1] = '\0';
if(l+l2-1>d)
memcpy(str,c+l+l2-1-d,sizeof(char)*(d+1));
else
memcpy(str,c,sizeof(char)*(l+l2));
}
else
{
c[l+l2] = '\0';
if(l+l2>d)
memcpy(str,c+l+l2-d,sizeof(char)*(d+1));
else
memcpy(str,c,sizeof(char)*(l+l2+1));
}
free(c);
}
void chen(char *a,int n)
{
int l = strlen(a);
if(n==10)
{
a[l] = '0';
a[l+1] = '\0';
}
else
{
int jin = 0;
for(int i = l-1; i >= 0; i--)
{
int temp = (a[i]-48)*n+jin;
jin = temp / 10;
temp = temp % 10;
a[i] = temp+48;
}
if(jin)
{
memcpy(a+1,a,sizeof(int)*(l+1));
a[0] = jin+48;
}
}
return;
}
int main(void)
{
char n[255];
char a[255];
char b[255];
int l,i,j;
int xun[100];
scanf("%s %d",n,&d);
strcpy(a,n);
l = strlen(n);
for(i = 1; i <= 10; i++)
{
chen(a,n);
if(str[d-1]==n[l-1])
{
xun[0] = i;
break;
}
strcpy(a,str);
}
for(i = 2; i <= d; i++)
{
strcpy(b,a);
for(j = 1; j <= 10; j++)
{
chen(a,n);
if(str[d-i]==n[l-i])
{
xun[i-1]=j;
break;
}
chen(a,b);
strcpy(a,str);
}
if(j==11)
{
printf("-1\n");
return 0;
}
}
a[0] = '1';
a[1] = '\0';
for(i = 0; i < d; i++)
chen(a,xun[i]);
printf("%s\n",a);
return 0;
}

这道题以前做过,先声明:这是一道复赛题,并不是初赛题,初赛是笔试的

具体核心算法是用高精度循环计算,当循环10000次无结果或有结果时中断退出,如果有结果输出值,否则输出-1

这是网络上一个C++解法
#include <iostream>
#include <cassert>
#include <cstring>
#include <cctype>

using namespace std;

const int LEN=100;

struct bigint{
int num[LEN];
bigint(){
memset(num, 0, sizeof(num));
}
bigint(const bigint& a){
int i;
for(i=0;i<LEN;i++)
num[i]=a.num[i];
}
bigint(int a) {
memset(num, 0, sizeof(num));
assert(a > 0);
int i = 0;
while(a > 0) {
num[i] = a % 10;
i++;
a = a / 10;
}
}
bigint(const char* str){
int i, j;
for (i = 0; str[i] != 0; i++) {
assert(isdigit(str[i]));
}
assert(str[0] != '0' && i <= LEN);
memset(num, 0, sizeof(num));
for (j = i - 1; j >= 0 ; j--)
num[j] = str[i - 1 - j] - '0';
}

bigint& operator=(const bigint& a){
int i;
for(i=0;i<LEN;i++)
num[i]=a.num[i];
return *this;
}

bigint operator+(const bigint& b) const{
bigint result;
int tot;
int i;
int add = 0;
for(i=0;i<LEN;i++){
tot = num[i] + b.num[i] + add;
result.num[i] = tot % 10;
add = tot / 10;
}
return result;
}

bigint operator*(const bigint& b) const{
bigint result;
int i, j, tot, add;
for(i=0;i<LEN;i++){
if(b.num[i]==0)continue;
add=0;
for(j=0;i + j < LEN;j++){
tot=result.num[i+j]+num[j]*b.num[i]+add;
result.num[i+j]=tot%10;
add=tot/10;
}
}
return result;
}

int getNum(int k) const{
return num[k - 1];
}

void output(int k) const {
int i;
for (i = k - 1; i >=0; i--) cout << num[i];
}
};

ostream& operator<<(ostream& out,const bigint& a){
int i; bool flag = false;
for(i=LEN-1;i>=0;i--) {
if (!flag) {
if (a.num[i] != 0) flag = true;
}
if (flag) {
cout << a.num[i];
}
}
return out;
}

int main () {
char buffer[1024];
int used[10];
int kk;
cin >> buffer >> kk;
bigint base(buffer);
assert(1 <= kk && kk <= LEN);

{char c; assert(!(cin >> c));}

int i, j;
bigint result(1);
bigint multi = base;
for (i = 1; i <= kk; i++) {
memset(used, 0, sizeof(used));
int p = base.getNum(i);
used[p] = 1;
int mm = 1;
bigint now = base;

//cout << "--------------" << endl;

while(1) {

//now.output(i); cout << endl;

bigint then = now * multi;
int q = then.getNum(i);
if (!used[q]) {
used[q] = 1;
now = then;
mm++;
}
else if (q != p) {
cout << -1 << endl;
return 0;
}
else break;
}

//cout << "--------------" << endl;

result = result * bigint(mm);

bigint temp(1);
for (j = 0; j < mm; j++) {
temp = temp * multi;
}
multi = temp;
}
cout << result << endl;

return 0;
}

解法pascal:
Program Circle;
Type
Arr = Array[1..101]Of Integer;

Var
i, j, p, k, code, L, num, tp: Integer;
s: String;
a, aa, time, b, temp: Arr;

Procedure Mutiply(a, b: Arr; Var c: Arr; t: Integer);
Var
i, j: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:=1 To t Do
For j:=1 To t-i+1 Do Begin
c[i+j-1] := a[i] * b[j] + c[i+j-1];
c[i+j] := c[i+j] + c[i+j-1] Div 10;
c[i+j-1] := c[i+j-1] Mod 10;
End;
End;

Procedure Mutiply(a: Arr; b: Integer; Var c: Arr; Var L: Integer);
Var
i: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:=1 To L Do Begin
c[i] := c[i] + a[i] * b;
c[i+1] := c[i] Div 10;
c[i] := c[i] Mod 10;
End;
If c[L+1] <> 0 Then Inc(L);
End;

Begin
Assign(Input, 'circle.in');
Assign(Output, 'circle.out');
ReSet(Input);
ReWrite(Output);

ReadLn(s);
Val(Copy(s, Pos(' ', s)+1, Length(s)-Pos(' ', s)), k, code);
Delete(s, Pos(' ', s), Length(s)-Pos(' ', s)+1);

For i:=1 To Length(s) Do Val(s[i], a[Length(s)-i+1], code);
aa := a;

FillChar(time, SizeOf(time), 0);
time[1] := 1;
L := 1;

For i:=1 To k Do Begin
For j:=1 To i Do b[j] := aa[j];
tp := b[i];
num := 0;

Repeat
Mutiply(b, a, b, i);
Inc(num);
Until (num > 10) Or (b[i] = tp);

If (b[i] <> tp) Then Begin
Write(-1);
Close(Input);
Close(Output);
Halt(0);
End;

temp := a;
For j:=1 To num-1 Do
Mutiply(a, temp, a, k);

Mutiply(time, num, time, L);
End;

For i:=L DownTo 1 Do Write(time[i]);

Close(Input);
Close(Output);
End.

pascal解法2:
program circle;
type
num=record
p:byte;
n:array[1..100] of integer;
end;
var
can:boolean;
code,k,i,j:integer;
st:string;
n,n2:num;
f,a:array[0..100] of num;
now:array[0..10] of num;
function multiply(x,y:num;k:byte):num;
var
i,j:integer;
z:num;
begin
z.p:=x.p+y.p-1;
if z.p>k then z.p:=k;
fillchar(z.n,sizeof(z.n),0);
for i:=1 to y.p do
begin
z.n:=z.n+x.n[1]*y.n;
for j:=2 to x.p do
begin
if i+j-1>k then break;
z.n[i+j-1]:=z.n[i+j-1]+x.n[j]*y.n;
z.n[i+j-1]:=z.n[i+j-1]+z.n[i+j-2] div 10;
z.n[i+j-2]:=z.n[i+j-2] mod 10;
end;
end;
while (z.n[z.p]>=10)and(z.p<k) do
begin
inc(z.p);
z.n[z.p]:=z.n[z.p-1] div 10;
z.n[z.p-1]:=z.n[z.p-1] mod 10;
end;
z.n[z.p]:=z.n[z.p] mod 10;
multiply:=z;
end;
function same(x,y:num;k:byte):boolean;
var
i:integer;
begin
same:=false;
for i:=k downto 1 do
if x.n<>y.n then
exit;
same:=true;
end;
begin
assign(input,'circle.in');
reset(input);
readln(st);
close(input);
val(copy(st,pos(' ',st)+1,length(st)-pos(' ',st)),k,code);
delete(st,pos(' ',st),length(st)-pos(' ',st)+1);
n.p:=k;
fillchar(n.n,sizeof(n.n),0);
if length(st)>k then delete(st,1,length(st)-k);
for i:=1 to length(st) do
n.n:=ord(st[length(st)-i+1])-48;
f[0].p:=1;f[0].n[1]:=1;a[0]:=n;
f[k].p:=1;f[k].n[1]:=-1;
for i:=1 to k do
begin
fillchar(now,sizeof(now),0);
now[0]:=n;n2.p:=1;n2.n[1]:=1;can:=false;
for j:=1 to 10 do
begin
now[j]:=multiply(now[j-1],a[i-1],i);
n2:=multiply(n2,a[i-1],k);
if same(now[j],now[0],i) then
begin
a:=n2;
n2.p:=1;n2.n[1]:=j;
f:=multiply(f[i-1],n2,100);
can:=true;
break;
end;
end;
if not can then break;
end;
assign(output,'circle.out');
rewrite(output);
for i:=f[k].p downto 1 do write(f[k].n);
writeln;
close(output);
end.

这好象是标准程序:
var r,str,ch:string;i,j,k,code,l:integer;
a:array[1..100]of byte;
b:array[1..100]of byte;
f:array[1..200]of integer;
e:array[1..10000]of string;
procedure pass;
var i:integer;
begin
for i:=1 to j do
if e[i]=r then
begin write(j-i+1); close(output); halt; end;
end;
begin
assign(input,'circle.in'); reset(input);
assign(output,'circle.out'); rewrite(output);
readln(r); close(input);
val(copy(r,pos(' ',r)+1,length(r)),k,code);
delete(r,pos(' ',r),length(r)-pos(' ',r)+1);
delete(r,1,length(r)-k);
j:=0;
for i:=1 to length(r) do b[i]:=ord(r[i])-48;
while j<10000 do
begin
inc(j); e[j]:=r;
for i:=length(r)+1 to k do e[j]:='0'+e[j];
for i:=1 to length(r) do a[i]:=ord(r[i])-48;
fillchar(f,sizeof(f),0);
for i:=1 to k do
for l:=1 to k do
begin
f[202-i-l]:=a[k+1-i]*b[k+1-l]+f[202-i-l];
f[201-i-l]:=f[202-i-l] div 10 +f[201-i-l];
f[202-i-l]:=f[202-i-l] mod 10;
end;
r:='';
for i:=201-k to 200 do r:=r+chr(f[i]+48);
pass;
end;
write(-1); close(output);
end.