1高精度的十进制运算

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,全国奥林匹克信息学联赛,辅导讲义,1,虽然最近五年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为,题 型,题目,与课内知识和编程基础相关,校门外的树、自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划、陶陶摘苹果、循环、谁拿了最多奖学金、2,k,进制数、数列,模拟,守望者的逃离、字符串的展开,构造法,均分纸牌、传染病控制、火星人、篝火晚会、作业调度方案、,纪念品分组,数据结构,字符近似查找、合并果子（堆排序）、栈、 FBI树（二叉树）、神经网络（图）、等价表达式 （栈）、明明的随机数 （快速排序）、Jam的计数法（字串处理）、,奖学金（排序）、统计数据（排序）、树网的核（图）,枚举法,虫食算、侦探推理,回溯法,选数、字串变换,动态规划,过河卒、数字游戏、加分二叉树、合唱队形、采药、过河、能量项链、金明的预算方案、开心的金明、,双塔问题（高精度）,、,矩阵取数游戏（高精度）,几何计算,矩形覆盖,2,联赛的科学性和公信力在增强,1、试题的难度和知识结构趋于合理。“抬高门槛、减少偏题”。这两年即没有可直译编程的基础题(最简单的题为排序题或动态规划),亦没有出现非“全军覆没”不可的偏题。,2、去年增加了模拟题；新增了排序类试题（普及组是多域数据的排序，提高组要求采用高效的排序算法）；高精度运算首次引入提高组。,3、对选手解题能力和综合素质的要求逐年提高。这两年没有单纯的搜索题和可直接套用经典算法的简单题，而数据结构类、构造类和动态规划类的试题增加，以考验选手的数学建模能力和创新意识。,4、分数的阶梯层次趋于科学。只懂语言、不懂数据结构和算法的选手拿低分；虽懂编程知识但缺乏数学思维和创新意识的选手拿中等分；综合素质强的选手拿高分（提高组满分的选手不多，因为有一道难度较大的综合题),。,3,高精度运算,排序思想及其应用,模拟法,图论,讲座内容,4,高精度运算,5,转换数据类型,加法运算,减法运算,乘法运算,除法运算,改善高精度运算的效率,分析近几年联赛中高精度类的试题,6,数据类型的转换,在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。,1、采用数串形式输入，并将其转化为整数数组。,2、用一个整数变量记录数据的实际长度（即数组的元素个数）,3、该数组的运算规则如同算术运算。,7,数据结构与转换方法,type,numtype= array1.500of word； 整数数组类型,var,a，b:numtype； a和b为整数数组,la，lb:integer；整数数组a的长度和b的长度,s:string； 输入数串,将数串s转化为整数数组a的方法如下：,k,length(s)；,for i1 to k do ak-i+1ord(si)-ord(0)；,8,加法运算ca+b(a、b、c为numtype类型),var,a,b,c:array1.201 of 0.9;,n:string;,lena,lenb,lenc,i,x:integer;,begin,write(Input augend:); readln(n);lena:=length(n); for i:=1 to lena do alena-i+1:=ord(ni)-ord(0);加数放入a数组,write(Input addend:); readln(n); lenb:=length(n); for i:=1 to lenb do blenb-i+1:=ord(ni)-ord(0);被加数放入b数组,i:=1;,while (i=lena) or(i=10 处理最高进位,then begin lenc:=i; ci:=1 end,else lenc:=i-1;,for i:=lenc downto 1 do write(ci); writeln 输出结果,end.,9,N进制运算,1、当前位规范由mod 10改为mod n,2、进位处理由div 10改为 div 10,3、运算规则不变,10,求回文数,若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。又如，对于10进制数87：,STEP1：87+78=165 STEP2：165+561=726,STEP3：726+627=1353 STEP4：1353+3531=4884,在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。,写一个程序，给定一个N（2N10，N=16）进制数m，m的位数上限为20。求最少经过几步可以得到回文数。如果在30步以内（包括30步）不可能得到回文数，则输出“impossible”,11,1.将数串s转化为整数数组m,设数串s=s,1,s,p,，串长为p。其中s,i,为第p-i+1位n进制数（1ip）。我们将s转化为整数数组m=mpm1，其中mi对应第i位n进制数。,type,mtype=array1.100of integer；,var,m：mtype；,按下述方法将s转化为整数数组m：,plength(s)；计算s的串长,for i1 to p do 从最高位开始计算整数数组m ,begin,kp-i+1；计算s,i,对应于的m数组下标,case si of转换s,i,af：mk10+ord(si)-ord(a)；,09：mkord(si)-ord(0)；,else 输出错误信息并退出程序；,end；case,end；for,12,2.判别整数数组m是否为回文数,function check (m： mtype) ：boolean；若整数数组m为回文数，则返回true，否则返回false,var i：integer；,begin,checkfalse；,for i1to do 返回m非回文数标志,if mimp-i+1 then exit；,checktrue；返回m为回文数标志,end；check,13,3.n进制加法运算,整数数组m,1,与其反序数m,2,进行n进制加法运算，得到结果m,1,procedure solve(var m,1,： mtype)；,var m,2,： mtype；,begin,for i1 to p do m,2,im,1,p-i+1；计算反序数m,2,for i1 to p do 由右而左逐位相加,begin,m,1,im,1,i+m,2,i；m,1,i+1 ；进位,m,1,im,1,imod n；确定当前位,end；for,if m,1,p+1 0 then pp+1；最高位进位,if check (m,1,)then 输出步数并退出程序；,end；solve,14,4.主程序,输入进制数n和数串s；,fillchar(m，sizeof(m)，0),将s转换为整数数组m；,if check(m),then begin 输出步数0；halt；end；then,步数初始化为0；,while 步数30 do,begin 步数+1；solve(m)；end；while,输出无解信息；,15,减法运算ca-b(a、b、c为numtype类型),var a,b,c:array1.200 of 0.9;,n,n1,n2:string; lena,lenb,lenc,i,x:integer;,begin,write(Input minuend:); readln(n1);,write(Input subtrahend:); readln(n2);,if (length(n1)length(n2) or (length(n1)=length(n2) and (n1n2),then begin n1n2,结果为负数,n:=n1;n1:=n2;n2:=n; write(-),end;,lena:=length(n1); lenb:=length(n2);,for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0);,for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0);,i:=1;,while (i=lena) or(i=lenb) do,begin,if ai1) do dec(lenc); 最高位的0不输出,for i:=lenc downto 1 do write(ci); writeln 输出差,end.,16,除法运算,1、整数数组除以整数（aa/i，a为整数数组，i为整数）,2、高精度除法xx/y(被除数x和除数y为整数，解决计算精度和循环节的问题),17,整数数组除以整数（aa/i，a为整数数组，i为整数）,我们按照由高位到底位的顺序，逐位相除。在除到第j位时，该位在接受了来自j+1位的余数（aj,aj+(j+1位相除的余数)*10）后与i相除。如果最高位为0（nln=0），则n的长度减1。,l0；余数初始化,for jla-1 downto 0 do begin按照由高位到底位的顺序，逐位相除,inc(aj，l*10)；接受了来自第j+1位的余数,laj mod i；计算第j位的余数,ajaj div i；计算商的第j位,end,；for,while (ala-1=0) do dec(la)；计算商的有效位数,18,高精度除法xx/y(被除数x和除数y为整数),高精度运算不仅能够扩大整数的值域，而且能够通过扩大小数的位数来减低除法的精度误差，甚至还可以计算出循环节。设,设小数部分的位数上限为limit；小数部分的指针为len；st为循环节的首指针；s为小数序列，其中si为第i位小数；posi为余数的位序列，其中posix表示余数为x的位序号。,记下第1位的余数和小数（posix mod y,1，s,1,（x mod y）*10,div y，x,x mod y）；然后按照除法的运算规则计算第2位、第3位的余数和小数。若下一位余数x先前出现过（posix0），则先前出现的位置posix为循环节的开始（st,posix），退出计算过程；否则依次类推，直至小数位数达到上限limit为止。,19,fillchar(s,sizeof(s),0);小数部分初始化,fillchar(posi,sizeof(posi),0); 小数值的位序列初始化,len,0;st,0; 小数部分的指针和循环节的首指针初始化,read(x,y);读被除数和除数,write(x div y);输出整数部分,x,x mod y;计算x除以y的余数,if x=0 then exit;若x除尽y，则成功退出,while lenlimit do若小数位未达到上限，则循环,begin,inc(len);posix,len;记下当前位小数，计算下一位小数和余数,x,x*10; slen,x div y;x,x mod y;,if posix0 若下一位余数先前出现过，则先前出现的位置为循环节的开始,then begin st,posix; break;end;then,if x=0 then break; 若除尽，则成功退出,end;while,20,if len=0,then begin writeln;exit;end;若小数部分的位数为0，则成功退出；否则输出小数点,write(.);,if st=0 若无循环节，则输出小数部分，否则输出循环节前的小数和循环节,then for i1 to len do write(si),else begin,for i1 to st-1 do write(si);,write();,for ist to len do write(si);,write();,end;else,21,乘法运算,1、高精度数组a乘整数I,2、两个高精度数组相乘,注意：,1、乘积用数组存储，如何定义数组的长度,2、乘法过程中，乘积数组的指针如何变化,22,高精度数组a乘整数i,设x为当前位相乘的结果和进位,x:=x+aj*i; 当前位乘积,aj:=x mod 10;当前位规整,x:=x div 10；计算进位,23,精确计算n的阶乘n!（7n50）,a,a1,a2,amax的值可以是0到9的任意数字,数组长度为,100,（因为,50!50,50,0,do,处理最高位的进位,begin,k:=k+1;ak:=x,mod,10;x:=x,div,10,end,end;,writeln;,for,i:=k,dowento,1 write(ai)输出a,end,.,25,乘法运算ca*b(a、b为numtype类型),1、积的位数为la+lb-1或者la+lb；,2、如果暂且不考虑进位关系，则a,i,*b,j,应该累加在积的第j+i-1位上,：,x:= ai*bj+ x div 10+ ci+j-1;,ci+j-1 := x mod 10;,3、可以先乘、后处理进位,26,var a,b,c:array1.200 of 0.9;,n1,n2:string; lena,lenb,lenc,i,j,x:integer;,begin,write(Input multiplier:); readln(n1);,rite(Input multiplicand:); readln(n2);,lena:=length(n1); lenb:=length(n2);,for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0);,for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0);,for i:=1 to lena do,begin,x:=0;,for j:=1 to lenb do对乘数的每一位进行处理,begin,x := ai*bj+x div 10+ci+j-1;当前乘积+上次乘积进位+原数,ci+j-1:=x mod 10;,end;,ci+j:= x div 10;进位,end;,lenc:=i+j;,while (clenc=0) and (lenc1) do dec(lenc); 最高位的0不输出,for i:=lenc downto 1 do write(ci); writeln,end.,27,改善高精度运算的效率,用一个整型数组来表示一个很大的数，数组中的每一个数表示一位十进制数字。这种方法的缺点是，如果十进制数的位数很多，则对应数组的长度会很长，并增加了高精度计算的时间。改善高精度运算效率的两种方法 扩大进制数 建立因子表,28,优化方法1、扩大进制数,一个Longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。,1、数据类型,type numtype=array0.9999 of longint；整数数组类型，可存储40000位十进制数 var a，n: numtype；a和n为10000进制的整数数组 st：string； 数串 la，ln integer； 整数数组a和n的长度,29,2、整数数组的建立和输出,当输入数串st后，我们从左而右扫描数串st，以四个数码为一组，将之对应的10000进制数存入n数组中。,具体方法如下：,readln(st)；输入数串stklength(st)；取得数串st的长度 for i0 to k-1 do begin 把st对应的整数保存到数组n中 j,(k-i+3) div 4-1； njnj*10+ord(sti+1)-48； end；for ln(k+3) div 4；,当得出最后结果a后，必须按照由次高位（ala-2）到最低位（a0）的顺序，将每一位元素由10000进制数转换成10进制数，即必须保证每个元素对应四位10进制数。,例如ai=0015(0ila-2)，对应的10进制数不能为15，否则会导致错误结果。我们按照如下方法输出a对应的10进制数：,write(ala-1)； 输出最高位 for ila-2 downto 0 do write(ai div 1000，(aidiv 100)mod 10，(aidiv 10)mod 10，aimod 10)；,30,注意,、作高精度算术运算时，运算规则不变，但求进位（div 10 ）和当前位（mod 10）时，需改为div 10000、mod 10000。,计算整数数组n-1时，从最低的n0位出发往左扫描，寻找第一个非零的元素（nj0，nj-1=nj-2=n0=0）。由于该位接受了底位的借位，因此减1，其后缀全为9999（nj= nj-1，nj-1=nj-2=n0=9999）。如果最高位为0（nln=0），则n的长度减1。,j0；从n0出发往左扫描，寻找第一个非零的元素,while (nj=0) do inc(j),；,dec(nj)；由于该位接受了底位的借位，因此减1,for k=0 to j-1 do nk9999；其后缀全为9999,if (j=ln-1)and(nj=0) then dec(ln)；如果最高位为0，则n的长度减1,31,彩票,现今，社会上流行着各种各样的福利彩票，彩票已经融入到了人们的日常生活之中。彩票之所以能吸引那么多的人们，玩法多是一大原因。其中有一类是从前N个自然数中选出M个（不计顺序）不同的号码，如果这M个号码与摇奖时摇出的M个中奖号码完全相符，那么就中了头奖。如现在已经有的：30选7，35选7，36选7，37选7,随着时间的推移，越来越多的人不满足于原来的玩法。为了追求更大的刺激，可供选择的号码和每注的号码个数越来越大，88选8，518选18，8888选68等等应运而生。但是，由此也衍生出了许多麻烦。由于数字越来越大，福彩中心的工作人员们已经无法用一般的计数器精确地计算出每一种彩票中头奖的概率。现在请你帮助他们，编一个程序：对于每一种玩法，能够快速准确地计算出中头奖概率的倒数。,输入:,n （M,N10,40,）,m （0M,1000）,输出：,在“N选M”的玩法中，中头奖的概率的倒数。,32,从N个数中（不计顺序）取出M个不同的数的取法共有C(N， M)种。这里C(N， M)表示组合数。因此，要使摇出的中奖号码与所选的号码完全相同，概率只有1 / C(N， M)。所以我们要求的值即为C(N， M)。根据组合数的计算公式：,我们可以直接地求解。但是由于题目中的N可能很大，所以我们必须要用到高精度计算。而在高精度计算中，运行的时间与参与运算的数的大小有直接的关系。所以，我们要使运算的中间结果尽可能地小。如果我们先把N(N-M+1)这M个连续的自然数乘起来，再依次除以1M就是一种不太明智的选择。,33,1. N和结果a为高精度数组,元素类型为Longint,代表4位一组的数字,即数组相当于一个10000进制的数，其中每一个数都是10000进制下的一位数。,2.我们可以先乘N除1，然后乘(N-1)除2，再乘(N-2)除3，最后乘(N-M+1)除M。因为连续的K个自然数的积一定能被K!整除，所以在这一过程中不会出现除不尽的情况。同时也使得中间结果比较小，从而提高了程序运行的速度。,a1;,for i=1 to m do,begin,aa*n; aa/i; nn-1;,end;for,34,readln(st)； readln(m)；,k：=length(st)；取得数串st的长度,for i：=0 to k-1 do begin 把N保存到数组n中,j,：=(k-i+3) div 4-1；nj：=nj*10+ord(sti+1)-48；,end；for,ln：=(k+3) div 4；,a0：=1 ;la：=1； 初始化数组a,for i：=1 to m do begin 计算组合数C(n，m),for j：=la-1 downto 0 do begin aa*n,for k：=ln-1 downto 1 do inc(aj+k，aj*nk)；,aj：=aj*n0；,end；for,l：=0；规范乘积a,for j：=0 to la+ln-1 do begin 处理进位,inc(l，aj)；aj：=l mod10000 ；l：=l div 10000；,end；for,35,if (ala+ln-10) 修改a数组的有效位数,then inc(la，ln),else inc(la，ln-1)；,l：=0； aa/i,for j,：=la-1 downto 0 do begin,inc(aj，l* 1000)；l：=aj mod i； aj：=aj div i；,end；for,while (ala-1=0) do dec(la)；,修改a数组的有效位数,j：=0； nn-1,while (nj=0) do inc(j),；,dec(nj)；,for k：=0 to j-1 do nk：=10000-1；,if (j=ln-1)and(nj=0) then dec(ln)；,修改n数组的有效位数,end,；for,write(ala-1)； 输出a,for i：=la-2 downto 0 do,write(ai div 1000，(aidiv 100)mod 10，(aidiv 10)mod 10，aimod 10)；,36,优化方法2、乘除时使用,因子表,任何自然数都可以表示为n=p,1,k1,*p,2,k2,*p,t,kt,的形式，p,1,，p,2,，p,t,为质因子。设num数组为自然数n，其中numi为因子i的次幂数(1ik)。显然，numk， numk-1， num2构成了一个自然数，该自然数可以用十进制整数数组ans存储。,ans的计算过程如下,ans0 1；将num转换为ans,for i2 to k do 枚举每一个因子,for j1 to numi do multiply (ans，i)；连乘numi个因子i,multiply的过程为高精度十进制运算中的乘法运算（ansans*I),有了自然数n的因子表num，可以十分方便地进行乘法或除法运算。例如整数x含有k个因子i，经过乘法或除法后，,37,我们按照上述方法依次处理x的每一个因子，得出的num即为积或商,procedure add(x，ob：longint)；ob=1，numnum*x；ob=-1，numnum/x,var,i：longint；,Begin,for i2 to x do 搜索x的每一个因子i,while (x mod i =0)do计算x含因子i的个数k。 numi= ,begin,inc(numi,， ob)；x x div i；,end；while,end；add,显然，如果n,1,=x,1,*x,2,*x,k,，,则可以通过连续调用,add(x,1,，1)；add(x,2,，1)；add(x,k,，1)；,得出n,1,对应的因子表num。如果n,2,=1/(x,1,x,2,x,k,)，则可以通过连续调用,add(x,1,，-1)；add(x,2,，-1)；add(x,k,，-1)；,得出n,2,对应的因子表num。注意，初始时num数组清零。,38,圣诞树,“叮叮当，叮叮当，铃儿响叮当”一年一度的圣诞节又来临了。,今年，霍比特人Timmy打算自己布置一颗圣诞树，瞧，他正往圣诞树上挂彩灯和苹果呢。Timmy的圣诞树是图一的一种形状：,这是一棵严格意义上的“二叉树”。然而，将其稍做变化如图二所示，就可以变成另一种形状不同的圣诞树！,Timmy一下来了兴趣，他有N个彩灯或苹果要挂在圣诞树上，因此，圣诞树必须有且仅有N个节点。你能帮助Timmy统计出这样的“圣诞树”一共有多少种么？,输入:,N（1,N, 0) then 若i位是最高位，则输出解,begin,for j：=i downto 0 do write(ansj)；,writeln；,end；then,变量num和过程add的定义如前所述。,42,分析近几年联赛中高精度类的试题,43,Hanoi双塔问题,【问题描述】 给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求: (1)每次只能移动一个圆盘； (2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序； 任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。 【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。 【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。,44,递推关系式,设fi代表i个尺寸的盘子移动到目标柱的最少步数。移动分三个步骤：,把前i-1尺寸的个盘子由起始柱移动到中间柱，移动步数为fi-1；,把第i个尺寸的盘子由起始柱移动到目标柱，移动步数为fi=2；,把前i-1个尺寸的盘子由中间柱移动到目标柱，移动步数为fi-1,因此递推关系式为：fi=fi-1*2+2=,(2in),边界：f1=2,由于n的上限为200，因此需要采用高精度加法和高精度乘法运算。为了确保不超时，建议按照10,4,进制存储。,45,readln(n);读盘子的尺寸数,fillchar(f,sizeof(f),0); f1,0:=1;f1,1:=2;f1=2,for i:=2 to n do计算fi=fi-1*2+2,begin fi:=fi-1*2; fi:=fi+2; end;,write(fn,fn,0);输出最高位,for i:=fn,0-1 downto 1 do按照max进制格式输出中间位,begin,if fn,i1000 then write(0);,if fn,i100 then write(0);,if fn,i10 then write(0);,write(fn,i);,end;,writeln;,46,矩阵取数游戏,【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个兀aij均为非负整数。游戏规则如下：,l 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；,2 每次取走的各个元素只能是该元素所在行的行首或行尾；,3 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分=被取走的元素值*2i，其中i表示第i次取数(从l开始编号)；,4 游戏结束总得分为m次取数得分之和。,帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。,【输入】输入文件gamein包括n+1行：,第l行为两个用空格隔开的整数m和m。,第2-n+l行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。,【输出】输出文件gameout仅包含1行，为一个整数，即输入矩阵取数后的最大得分。,【限制】60的数据满足：1n，m30，答案不超过10,16,100的数据满足：ln，m80，0a,ij,1000,47,给出一个N*M的矩阵，每次取每行的行首和行末的一个数，得分=被取走的元素值*2,i,（i表示第i次取数）。求最大得分。,动态规划。对每行分别处理求最大得分。,定义Fi,j表示当前从某行的第i个元素取到第j个元素的最大得分。有两种取法：,取末尾的第j个元素，得分为（Fi,j-1+Gj）*2；,取首部的第i个元素，得分为(Fi+1,j+Gi)*2；,显然Fi,j=max(Fi,j-1+Gj，Fi+1,j+Gi)*2。,边界：Fi,i=Gi*2。（1im）,当前行的最大得分为F1,m。累加n行的最大得分即为问题解。注意：由于最终答案位数在30位左右，需要高精度计算。为了确保不超时，建议按照10,6,进制存储。,48,计算s行的状态转移方程,function calc(s:longint):anstype;,var i,j,l:longint;,temp1,temp2:anstype;,begin,fillchar(f,sizeof(f),0);状态转移方程初始化为,for i:=1 to m do fi,i:=,maps,i*2,; fi,i,为s行的第i个元素值,for l:=2 to m do枚举区间长度,for i:=1 to m-l+1 do枚举区间首指针,begin,j:=i+l-1;计算尾指针,temp1,:=,(fi+1,j+maps,i)*2,;,取区间首元素,temp2,:=,(fi,j-1+maps,j)*2,;,取区间尾元素,if,temp1 temp2,取两个方案的大者作为该区间的状态转移方程值,then fi,j:=temp1,else fi,j:=temp2,end;,calc:=f1,m,返回,s,行的状态转移方程值,end;,49,主程序,readln(n,m);,读矩阵规模,for i:=1 to n do读矩阵元素（存储方式为高精度数组）,for j:=1 to m do,begin mapi,j0:=1;read(mapi,j1)；end;,fillchar(ans,sizeof(ans),0);最大得分初始化为,for i:=1 to n do,ans:=ans+calc(i);,累加n行的状态转移方程值,write(ansans0);输出最大得分的最高位,for i:=ans0-1 downto 1 do按照由高至低的顺序输出每一位值,begin,str(ansi,st);将最大得分的第i位转化为数串,while length(st)limitl do insert(0,st,1);第i位实际位数不足位，串首添,write(st)输出第i位,end;,50,麦森数,【问题描述】形如2,P,-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2,P,-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。,任务：从文件中输入P（1000P3100000），计算2,P,-1的位数和最后500位数字（用十进制高精度数表示）,【输入格式】文件中只包含一个整数P（1000P3100000）,【输出格式】第一行：十进制高精度数2,P,-1的位数;第2-11行：十进制高精度数2,P,-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）,不必验证2,P,-1与P是否为素数。,51,使用倍增思想，优化幂运算,首先，看一个简单的例子已知整数a，计算a,17,。很显然，一种最简单的方法就是令b=a，然后重复16次进行操作b=b*a。这样，为了得到a,17,，共进行了16次乘法。,现在考虑另外一种方法，令a,0,=a，a,1,=a,2,，a,2,=a,4,，a,3,=a,8,，a,4,=a,16,，可以看出，a,i,=a,i-1,2,，(1i4)。于是，得到a,0,，a,1,，a,2,，a,3,，a,4,共需要4次乘法。而a,17,= a*a,16,=a,0,*a,4,，,也就是说，再进行一次乘法就可以得到a,17,。这样，总共进行5次乘法就算出了a,17,。,52,已知a，计算a,n,:,将n表示成为二进制形式，并提取出其中的非零位，即n=2(b,1,)+2(b,2,)+2(b,w,)， (2(i)=2,i,)不妨设b,1,b,2,0 do由低位向高位方向逐位分析p的每一个二进制位,begin,if p mod 2=1 若p的当前二进制位为1，则连乘当前项，取乘积的后500位,then begin,ansans*l；,end,;then,p:=p div 2;处理高一位,ll,2,；,end;while,dec(ans0);计算2,p,-1,for i:=499 downto 0 do按照50位数一行的格式输出2,p,-1的后500位数,begin,write(ansi);,if i mod 50=0 then writeln;,end;for,55,循环,【问题描述】,乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。,众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：,56,这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？,注意：,1 如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。,2 如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k位都相同。,【输入文件】输入文件,circle.in,只有一行，包含两个整数n（1n10,100,）和k（1k100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。,【输出文件】输出文件,circle.out,包括一行，这一行只包含一个整数，表示循环长度。如果循环不存在，输出-1。,57,问题的规模要求采用高精度计算,本题要求计算n（1n10,100,）的正整数次幂的最后k（1k100）位的循环长度，因此必须采用k位高精度运算。不仅每次乘幂运算需要通过高精度乘法保留后k位，而且由于最小循环长度是任何整数类型无法容纳的，因此其计算过程也需要用到k位高精度加法。,58,必须采用倍增思想提高时效,如果采用简单的连乘运算，是根本不可能满足时效要求的，只能采用倍增思想逐位递推：先保证第1位循环，求出最小的循环长度l,1,；接下来计算第2位循环的最小循环长度：连乘 ，直至出现2位循环为止。此时得出2位的最小循环长度l,2,；然后连乘 ，直至出现3位循环为止，由此得出第3位循环的最小循环长度；，依次类推，直至递推出第k位的最小的循环长度l,k,。在计算第i（1ik）位循环时，如果连乘了10次后没有结果，则输出无解信息。因为第i位所有可能出现的数字都已经出现，因此不可能递推出长于i位的循环节了。,59,数据结构,设,参与运算的两个操作数为整数数组p和tempp；辅助的整数数组为stp和pp,循环长度为整数数组tempt,该数组的长度为tottemp；,连乘一次增加的次幂数为整数数组t，该数组的长度为tott；,60,输入信息，建立整数数组,readln(st); 读输入串,st1:=copy(st,1,pos( ,st)-1); delete(st,1,pos( ,st);val(st,k,ok);从输入串中截出底数st1和正整数次幂的最后位数，将其转换为整数k,if length(st1)10 then 输出-1若连续乘了10次仍然没有出现循环，则输出无解信息。因为第kk位所有能出现过的数字都已经出现过了，仍没有我们想要的n的第kk位，就表示不可能循环了,end; while ,tempp:=pp; 当前位乘幂pp暂存tempp,t:=tempt;tott:=tottemp循环长度tempt暂存t,end; for ,for i:=tott downto 1 do write(tempti);输出循环长度,writeln;,end;,63,