[問題] TIOJ 1324

[vincent97198 (萌新冒險者)]

問題來源：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://www.ptt.cc/bbs/Prob_Solve/M.1580898974.A.36F.html
推 alan23273850: 反例: a=2, k=0, n=4
推 LPH66: k > 0 應該就對了, 所以你不能直接 % phi(n)
→ alan23273850: k=1 還是錯啊，2^1 不同餘於 2^(1+2) mod 4
→ vincent97198: 看來我的方法不可行請問要如何解決不互質的情況呢？
推 alan23273850: 總覺得這題是要用程式的方式找出循環節，不需要特別
→ alan23273850: 針對互質&不互質作討論
→ alan23273850: 像 4^k = 4 (mod 6) for all k，這個事實不跑跑看怎
→ alan23273850: 麼會知道呢？
→ vincent97198: 謝謝alan大 我再想看看
推 oToToT: 或許你可以查查擴展歐拉定理，雖然這應該不是正確的學術名
→ oToToT: 詞，不過滿多中國選手會用的w