[CF 303D]Rotatable Number解题报告

 题目翻译


题解

出于可看性,就不用那么严格的数学语言讲了……

首先明确一下“循环数”的定义:比如142857,它乘以1,2,3,4,5,6(必须是连续的这些数)能不重不漏地得到142857的所有循环排列。

假设我们拿到了一个(十进制下的)循环数,不妨取142857.令x=0.142857142857……显然它是一个有理数,设为最简分数q/p((p,q)=1)。
因为x是一个无限纯循环小数,所以(10,p)=1.

我们考察这两组数:

第一组:x=0.142857142857……,2x=0.285714285714……,3x=0.428571428571……,4x=0.571428571428……,5x=0.714285714285……,6x=0.857142857142……

第二组:x=0.142857142857……,10x=1.428571428571……,100x=14.285714285714……,1000x=142.857142857142……,10000x=1428.571428571428……,100000x=14285.714285714285……

根据循环数的定义,第一组和第二组数的小数部分必然相同(不考虑排列顺序,下同),反之亦然。
也就是说,命题:“{q/p,2q/p,…,6q/p}和{q/p,10q/p,…,10^5q/p}两组数的小数部分相同”等价于命题:“142857是循环数”。
由于(p,q)=1,上述小数部分只由分子模p的余数决定。
即,{q,2q,…,6q}和{q,10q,…,10^5q}(模p意义下)这两个无序集合是相同的。下面我们将两个模p意义下的无序集合相同称为这两个集合“同构”(没错,就是为了逼格)

在进一步讨论之前,我们先来看p的取值。由于(p,q)=1,故q对模p有乘法逆元q’。将两个集合都乘以q’,得到{1,2,…,6}和{1,10,…,10^5}同构。
显然{1,10,…,10^5}中有一个数模p余2.事实上它是100,显然,第二个集合与{10^2,10^3,…,10^7}同构(不信你自己算一下尾数),即,第二个集合与{2*1,2*10,…,2*10^5}同构,故第一个集合与{2*1,2*2,…,6*2}同构,将其中的2,4,6去掉,我们发现,{1,3,5}和{8,10,12}同构。
易证{1,2,…,6}中没有p的倍数(否则x乘这个数得到一个整数,还怎么玩……),所以p>=7.
那么,8在{1,3,5}中对应谁呢?8和它对应数的差值不是0,而且是p的倍数,故差值>=p。所以8最大能对应1,但{1,3,5}中没有比1小的了,故8只能对应1.也就是说,8-1是p的倍数,根据前面讨论的p>=7,一定有p=7.(这里可以看出循环节长度一定是偶数,若为奇数,例如5,我们就得到了{1,3,5}对应{6,8,10},但6最大对应0,矛盾)。

显然上述论证在n≠6的时候仍然成立:p=循环节长度+1.
所以我们就可以用一种充满逼格的写法:{1,2,…,p-1}和{10^0,10^1,…,10^(p-2)}同构。
你有没有一种怪怪的感觉……

没错,10^1,…,10^(p-2)中没有一个模p余1的数(即,1~p-2都不是φ(p)),那么真相只有一个:

p是质数,而且10是p的一个原根!

而反过来,如果p是质数而且10是p的一个原根,那么{1,2,…,p-1}和{10^0,10^1,…,10^(p-2)}同构,而且10^(p-1)=1(mod p),换言之,1/p的小数循环节长度为p-1,而且这个循环节所组成的数一定是循环数。

事实上,前面所做的论证可以推广至其他进制,只需要将10换成进制基数b即可。

我们再来看原题:给出n,x,求最大的b

那么原题就等价于:

给出n,x,求最大的b

对一个素数p,如何判断a是否为p的原根呢?其实只需要检查p-1的所有因数d[1],d[2],…,d[k],如果某个1<=i<=k使得a^d[i]=1(mod p)则a不是p的原根,否则a是p的原根。(其原理是:若a在模p下的指数是t,又有a^(p-1)=1(mod p),则必有t|p-1)。
用快速幂实现,复杂度为O(sqrt(p)logp)。

整个算法是这样的:
1.判断n+1是否为素数,不是素数则无解
2.从x-1向下枚举b,用上述算法检测每个b是否是答案
3.若最终没有找到答案则无解。

题目限制是n<=5*10^6,x<=10^9.算法的复杂度最大可能是O(x*sqrt(n)*logn),但实际上只需要枚举很少的b,因为原根其实挺多的……总之这么就能过。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注