[问题] TIOJ 1324

楼主: vincent97198 (萌新冒险者)   2020-02-05 18:36:10
问题来源:https://tioj.ck.tp.edu.tw/problems/1324
问题:
底数与要除的数不互质时 a^k (mod n) = a^(k+phi(n)) (mod n)还成立吗?
还是我搞错解题方向了?
已有的想法:
用欧拉定理化简掉超大的指数
我的程式码(只拿了32分)
https://ideone.com/gYneXP
作者: alan23273850   2020-02-05 18:51:00
反例: a=2, k=0, n=4
作者: LPH66 (-6.2598534e+18f)   2020-02-05 21:30:00
k > 0 应该就对了, 所以你不能直接 % phi(n)
作者: alan23273850   2020-02-06 11:47:00
k=1 还是错啊,2^1 不同余于 2^(1+2) mod 4
楼主: vincent97198 (萌新冒险者)   2020-02-06 16:09:00
看来我的方法不可行请问要如何解决不互质的情况呢?
作者: alan23273850   2020-02-06 18:09:00
总觉得这题是要用程式的方式找出循环节,不需要特别针对互质&不互质作讨论像 4^k = 4 (mod 6) for all k,这个事实不跑跑看怎么会知道呢?
楼主: vincent97198 (萌新冒险者)   2020-02-06 22:42:00
谢谢alan大 我再想看看
作者: oToToT (屁孩)   2020-02-07 13:20:00
或许你可以查查扩展欧拉定理,虽然这应该不是正确的学术名词,不过满多中国选手会用的w

Links booklink

Contact Us: admin [ a t ] ucptt.com