POJ3358 Period of an Infinite Binary Expansion 解题报告

February 10, 2010 / ACM, 解题报告

写于2007-08-26 20:54

题目大意:

给出十进制数p和q,将p/q表示成二进制小数,并求出二进制小数的循环节起始位置和循环节的长度。

输入:

p/q ( p >= 0, q > 0 , p,q < 2e10 )

输出:

Case #n: s,l ( n第几个测试用例,s为循环节起始位置,l为循环节的长度)

解法类型:数论

解题思路:

求循环节最朴素的算法是通过迭代法求出第一个重复出现的余数,如果p与q互质,令X1= p, Xk = X(k-1) * 2 mod q, 直到Xn = p, 则循环节长度为n-1,但是,这道题给的数据范围很大,如采用这种算法,会执行很多次操作,可能多达数亿次,加之求余运算相对较慢,这种算法的时间效率就不能得到保证,而此题的时间限制是1S,因而需要寻求更优的算法。

首先要将p/q化简,通过gcd(p,q)求得二者的最大公约数,并同时除去此数,可优化下面的计算,接着先求出循环节的起始位置,由于求的是二进制小数,所以需要对分母进行分解,p/q =p/(r2m)=(t+kr)/(r2m)=(t/r+k)1/(2m)。由于p与q互质可知t与r也互质,而k为整数,对求小数部分没影响,又1/(2m)只会使小数点向左偏移,只影响循环节的起始位置,对长度没影响,由于r与t,2都素质,可知t/r的循环节起始位置为1,又小数点向左偏移m位,因此p/q的循环节起始位置为m+1。下面的问题是求出t/r的循环节长度,而这个问题可转化为求满足t2^k = t(mod r )的最小k值,上式可进一步化简,(t2^k) mod r= (t mod r)(2^k mod r ) mod r=t(2^k mod r ) mod r = t,所以问题简化为求满足2^k = 1(mod r)的最小k值。

上述问题如果只是简单枚举,当r为素数时可能需要计算r-1次,运算相当大,于是,这里引入了欧拉定理。

任意一个整数n都可以表示为其素因子的乘积为:n=p1q1p2q2……pmqm,则它的欧拉函数为:Φ(n)=p1(q1-1)(p1-1)p2(q2-1)(p2-1)……pm(qm-1)(pm-1),进一步简为Φ(n)=n(1-1/p1)(1-1/p2)……*(1-1/pm),如果a与n互质,则a^Φ(n) = 1(mod n)。