tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

NOIP2005普及组circle循环


NOIP2005 普及组 circle 循环 【问题描述】 乐乐是一个聪明而又勤奋好学的孩子。 他总喜欢探求事物的规律。 一天, 他突然对数的正整数次幂产生了兴趣。 众所周知,2 的正整数次幂最后一位数总是不断的在重复 2,4,8,6,2,4,8,6……我们说 2 的正整数次 幂最后一位的循环长度是 4(实际上 4 的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,

其余 的数字的正整数次幂最后一位数也有类似的循环现象:这时乐乐的问题就出来了:是不是只有最后一位才有这样的 循环呢?对于一个整数 n 的正整数次幂来说,它的后 k 位是否会发生循环?如果循环的话,循环长度是多少呢? 注意: 1. 如果 n 的某个正整数次幂的位数不足 k,那么不足的高位看做是 0。 2. 如果循环长度是 L,那么说明对于任意的正整数 a,n 的 a 次幂和 a + L 次幂的最后 k 位都相同。 【输入文件】 100 输入文件 circle.in 只有一行, 包含两个整数 n(1 ? n< 10 )和 k(1 ? k ? 100), 和 k 之间用一个空格隔开, n 表示要求 n 的正整数次幂的最后 k 位的循环长度。 【输出文件】 输出文件 circle.out 包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。 【样例输入】 32 2 【样例输出】 4 【数据规模】 对于 30%的数据,k ? 4;对于全部的数据,k ? 00。

循环 2 3 4 5 6 7 8 9 2、4、8、6 3、9、7、1 4、6 5 6 7、9、3、1 8、4、2、6 9、1

循环长度 4 4 2 1 1 4 4 2

第 1 页

2009-06-08

NOIP2005 普及组 circle 循环
从个位开始判断:几轮循环后,如果出现 1(个位数字的第 1 次),计算循环长度 j,连续自乘幂 j 次,转(2); 如果没有出现 1,出现了其它数字,则循环节不存在,输出-1 后结束。 (1) 依次判断十位……。 (2) 每个数字的循环长度纪录在 circle 数组。 (3) 如果能计算至最高位,则 circle 数组的每 1 个元素连乘就是要求的 n 的正整数次幂的最后 k 位的循环长度。 [例] n=32 32 乘幂 1 2 3 4 5 积 32 1024 32768 1048576 33554432 十位 3 2 6 7 3 个位 2 4 8 6 2 2 3 4 5 j

32 的循环长度=4,但程序是先判断个位成立后 sc:=ss; ij:=b[a[j,i]]; circLe[i]:=j-1;{循环长度=幂次方-1,并记录在 circle 数组里, circle[1]=5-1=4} for ij:=2 to j-1 do muLti(ss,sc,ss); {初值 ss=32,经过 ss 自乘 3 次=104876,在十位乘 1 次=33554432, circle[2]=1} circle[1] *circle[2]=4*1=4

第 2 页

2009-06-08

NOIP2005 普及组 circle 循环 const max=100; type hint=array[0..max]of Longint; var st,s1,s2:string; k,ok:Longint; a:array[1..11]of hint;{某 1 位的循环长度一定<11,在第 11 次乘幂不能出现初始值,则循环不成立} b:array[0..9]of Longint; circLe:array[0..max]of Longint; tot:hint; n,start:hint; sc,ss:hint; i,j,ij,L,m:Longint; procedure muLti(var a:hint;b,c:hint); var i,j,e:Longint; begin fiLLchar(a,sizeof(a),0); for i:=0 to k-1 do for j:=0 to k-1 do if i+j<=k-1 then inc(a[i+j],b[i]*c[j]); e:=0; for i:=0 to k-1 do begin a[i]:=a[i]+e; e:=a[i] div 10; a[i]:=a[i] mod 10; end; end; procedure muLt(var a:hint; b:Longint); var i,e:Longint; begin for i:=0 to a[max] do a[i]:=a[i]*b; e:=0; for i:=0 to a[max]+1 do begin a[i]:=a[i]+e; e:=a[i] div 10; a[i]:=a[i] mod 10; end; if a[a[max]+1]>0 then a[max]:=a[max]+1; end;

第 3 页

2009-06-08

NOIP2005 普及组 circle 循环 begin assign(input,'circLe.in'); reset(input); assign(output,'circLe.out'); rewrite(output); readLn(st); s1:=copy(st,1,pos(' ',st)-1); deLete(st,1,pos(' ',st)); s2:=st;
{ s1= st 的第一个至空格前所有字符,赋值后,删除 st 的第一个至空格所有字符,s2= st 空格后所有字符}

deLete(st,1,pos(' ',st)-1); s2:=st; whiLe pos(' ',s2)>0 do deLete(s2,pos(' ',s2),1);
{赋值后,删除 st 的第一个至第一个空格所有字符,s2= st 空格后所有字符,可能存在连续空格}

vaL(s2,k,ok); {字符型 S2 转换为数值型 K} s2:=copy(s1,Length(s1)-k+1,k); {S1 后长度 k-1 位赋值给 S2} whiLe Length(s2)<k do s2:='0'+s2; {如果 n 的某个正整数次幂的位数不足 k,那么不足的高位看做是 0} for i:=1 to k do n[k-i]:=ord(s2[i])-48; {S1 后长度 k-1 位转换为数值型 n[k-i]} n[max]:=k-1; {求字符型 S2 长度} start:=n; ss:=n; a[1]:=n; {n,ss,start 都是一维数组 hint, a 是二维数组,直接赋值一行数据?a[1]是个一维数组} for i:=0 to k-1 do begin
{b:array[0..9]of Longint}

fiLLchar(b,sizeof(b),0); b[a[1,i]]:=1; {第 i 位数字第 1 次出现,假设 b[a[1,i]]=b[9]=1,表示第 i 位数字第 1 次是 9} j:=2; {循环长度的初值=2} whiLe true do begin muLti(a[j],a[j-1],ss); {ss=n,a[j-1]=a[1]=n,自乘} if b[a[j,i]]=0
{a:array[1..11,0..100] of longint,共 0..9,乘 11 次一定会出现重复数字,但不能确定是第 1 次的值,如果第 j 次乘幂后,这个数字是 首次出现(多数情况是这样), b[a[j,i]]=b[任何 1 个没有出现的数字]=j, 表示第 i 位数字第 j 次出现的}

then begin b[a[j,i]]:=j; inc(j); end eLse begin sc:=ss; ij:=b[a[j,i]]; if ij<>1{某一位数值出现了循环,但不是初始值,则这个循环节不是所求的,中断整个程序,一般不会出现在个位} then begin writeLn(-1); cLose(input); cLose(output); haLt;end; circLe[i]:=j-1;{循环长度=幂次方-1,并记录在 circle 数组里} for ij:=2 to j-1 do muLti(ss,sc,ss); {改变了 SS,使 SS 是初始的(j-1)-2+1 次幂} j:=2; break; {退出 whiLe 循环,检测下 1 位的循环长度} end; end; end; fiLLchar(tot,sizeof(tot),0); tot[0]:=1; for i:=1 to k do muLt(tot,circLe[i-1]); for i:=k-1 downto 0 do if tot[i]>0 then break; for j:=i downto 0 do write(tot[j]); cLose(input); cLose(output); end.

第 4 页

2009-06-08


推荐相关:

NOIP2005普及组circle循环

NOIP2005普及组circle循环_学科竞赛_高中教育_教育专区。NOIP2005普及组circle循环NOIP2005 普及组 circle 循环 【问题描述】 乐乐是一个聪明而又勤奋好学的孩子。 他...


noip2005普及组解题报告

noip2005普及组解题报告_建筑/土木_工程科技_专业资料。noip2005普及组解题报告noip...【输出文件】 输出文件 circle.out 包括一行,这一行只包含一个整数,表示循环...


NOIP2005复赛普及组

NOIP2005 普及组复赛——第 2 页共 3 页 四、循环(circle.pas/c/cpp) 【问题描述】 乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他...


pascal普及组复赛

【输出文件】 输出文件 circle.out 包括一行,这一行只包含一个整数,表示循环...NOIP2005普及组复赛试题... 20页 1下载券 NOIP2006普及组复赛试题... 21页 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com