作者vincent97198 (萌新冒险者)
看板Prob_Solve
标题[问题] TIOJ 1324
时间Wed Feb 5 18:36:10 2020
问题来源：
https://tioj.ck.tp.edu.tw/problems/1324
问题：
底数与要除的数不互质时 a^k (mod n) = a^(k+phi(n)) (mod n)还成立吗？
还是我搞错解题方向了？
已有的想法：
用欧拉定理化简掉超大的指数
我的程式码（只拿了32分）
https://ideone.com/gYneXP
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.33.208.245 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1580898974.A.36F.html
1F：推 alan23273850: 反例: a=2, k=0, n=4 02/05 18:51
2F：推 LPH66: k > 0 应该就对了, 所以你不能直接 % phi(n) 02/05 21:30
3F：→ alan23273850: k=1 还是错啊，2^1 不同余於 2^(1+2) mod 4 02/06 11:47
4F：→ vincent97198: 看来我的方法不可行请问要如何解决不互质的情况呢？ 02/06 16:09
5F：推 alan23273850: 总觉得这题是要用程式的方式找出循环节，不需要特别 02/06 18:09
6F：→ alan23273850: 针对互质&不互质作讨论 02/06 18:09
7F：→ alan23273850: 像 4^k = 4 (mod 6) for all k，这个事实不跑跑看怎 02/06 18:10
8F：→ alan23273850: 麽会知道呢？ 02/06 18:10
9F：→ vincent97198: 谢谢alan大 我再想看看 02/06 22:42
10F：推 oToToT: 或许你可以查查扩展欧拉定理，虽然这应该不是正确的学术名 02/07 13:20
11F：→ oToToT: 词，不过满多中国选手会用的w 02/07 13:20