当然看不懂的同学就不要看了自己补数论去.
当年写这题,看到最后的离散对数就不会了直接看题解发现题解是O(n)的...
事实上这个是我在NOI那几天脑洞想到这道题之后才发现哦艹官方解法是线性的!
我给出一个O(n^0.5)的解法,以下.
首先我们不妨假设1/n是纯循环小数,又设r是1/n在k进制下的一个循环节,r不一定是最小的.
那么我们考虑把1/n乘上k^r,相当于在k进制下左移r位,可以看出的它和1/n的小数部分是一样的.
比如1/5在2进制下是0.{0011}.乘上2^4为16/5变成了11.{0011}.注意我用二进制写的.
那么我们看出,((k^r)/n)-(1/n) 是一个整数
玩玩这个式子发现其等价于 n | (k^r-1)
再玩玩,我们发现原问题转化为了
求最小的r,满足
k^r=1 (mod n).
由欧拉定理这样的r显然在[1..phi(n)]范围内存在,故我们"纯循环"的假设是对的.
这个是一个离散对数问题,解决离散对数问题的标准方法是Baby Step Giant Step,也不难写.
但是这道题我们面前是一个特殊的离散对数,是否可以利用等式右边为1而乱搞搞出更简单的解法呢?
可以.你观察观察,发现一个规律: 最小的r总满足 r | phi(n)
证明一下呀?这个证明挺有趣的,你应该自己想想.
===========================防剧透==============================
以下是我在NOI那几天YY出的证法.
我们现在需要证明一个引理,如果这个引理成立则上面的结论(r | phi(n))成立.
引理:
对于互素的a,b,以及0<c<phi(b).我们有
a^c=1 (mod b)
是
a^(c,phi(b))=1 (mod b)
的充要条件.
证明:必要性显然,下证充分性.
由欧拉定理有a^phi(b)=1 (mod b).
于是我们现在知道了
a^phi(b)=1 (mod b)
a^c=1 (mod b)
显然a^(phi(b)-c)=1 (mod b)
于是我们知道了
a^c=1 (mod b)
a^(phi(b)-c)=1 (mod b)
把每两个方程写成无序数对,看出我们可以从
(phi(b),c)得到(c,phi(b)-c).
我们不妨假设c>phi(b)-c(相反的情况一样),于是我们又可以得到
(phi(b)-c,c-(phi(b)-c))
这就是高中数学里面的一种求gcd的方法叫更损什么什么的...
可以很简单地证明这个更损什么什么的等价于欧几里得.
顺便说说这个更损什么什么的时间复杂度是O(n)的,OI里写=作死.
一直搞下去就可以得到
((phi(b),c),0)
意义为
a^0=a^(phi(b),c)=1 (mod b).
这里你可以看出最小的r必定整除phi(n)
于是我们枚举phi(n)的约数即可O(n^0.5)搞完了.
废话一下,这里(a,b)=gcd(a,b).[a,b]=lcm(a,b).
退役了懒得给标程了.有问题的话请自己思考思考思考之后提出,虽然我也不大可能回答了233.
然后更正,时间是O(lgn*n^0.5),枚举约数的时候还要快速幂.
可以用AC大神的拓展BSGS去掉时间复杂度里面的lgn,如果你会
顺便我做过的离散对数题除了一个clever Y都是模数是素数的,出拓展BSGS掉rp.
全数据83ms,当前Rank 1.作为在语言歧视比BZOJ还严重的RQ上面,我一个P党能这么快挺不错的了.
退役了,挺想保存自己的Rank 1的...但是我还是把想法的实践贴出来吧.
[自重].
如果你只是去NOIP的话,完全不用做这道题,因此也没有抄代码的必要了,如果你是去NOI的话我相信你的素质.
很短(比起很多树套树套树的题),希望RQ不吞缩进.
{$INLINE ON}
program rq368;
var b,k:int64;
function phi(n:int64):int64;
var i:longint;
begin
phi:=n; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then begin
phi:=phi div i*(i-1); while n mod i=0 do n:=n div i;
end; if n<>1 then phi:=phi div n*(n-1);
end;
function exp(a,b,mo:int64):int64;
begin
a:=a mod mo; exp:=1; while b<>0 do begin
if b and 1=1 then exp:=int64(exp)*a mod mo;
a:=int64(a)*a mod mo; b:=b>>1;
end;
end;
function dislog(a,b:int64):int64; (* This function returns the minimal c satisfying that a^c=1(mod b) *)
var i,j,pb:longint;
begin
pb:=phi(b); dislog:=pb;
for i:=1 to trunc(sqrt(pb)) do if pb mod i=0 then begin
j:=pb div i; if exp(a,i,b)=1 then exit(i)
else if exp(a,j,b)=1 then dislog:=j;
end;
end;
begin
readln(b,k); writeln(dislog(k,b));
end.