UVA 11549 Calculator Conundrum

题意

给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。

这是一个循环的过程,你要找出在这个循环节中最大的数。

思路

首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。

取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。

找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。

代码

Floyd判圈法,数学方法求前n位。

 

Leave a Reply

Scroll to top