PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] TIOJ 1324

看板Prob_Solve (計算數學 Problem Solving)作者 (萌新冒險者)時間4年前 (2020/02/05 18:36), 編輯推噓4(4推 0噓 7→)
留言11則, 4人參與, 4年前最新討論串1/1
問題來源：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
推
02/05 18:51, 4年前 , 1F
反例: a=2, k=0, n=4
02/05 18:51, 1F
推
02/05 21:30, 4年前 , 2F
k > 0 應該就對了, 所以你不能直接 % phi(n)
02/05 21:30, 2F
→
02/06 11:47, 4年前 , 3F
k=1 還是錯啊，2^1 不同餘於 2^(1+2) mod 4
02/06 11:47, 3F
→
02/06 16:09, 4年前 , 4F
看來我的方法不可行請問要如何解決不互質的情況呢？
02/06 16:09, 4F
推
02/06 18:09, 4年前 , 5F
總覺得這題是要用程式的方式找出循環節，不需要特別
02/06 18:09, 5F
→
02/06 18:09, 4年前 , 6F
針對互質&不互質作討論
02/06 18:09, 6F
→
02/06 18:10, 4年前 , 7F
像 4^k = 4 (mod 6) for all k，這個事實不跑跑看怎
02/06 18:10, 7F
→
02/06 18:10, 4年前 , 8F
麼會知道呢？
02/06 18:10, 8F
→
02/06 22:42, 4年前 , 9F
謝謝alan大 我再想看看
02/06 22:42, 9F
推
02/07 13:20, 4年前 , 10F
或許你可以查查擴展歐拉定理，雖然這應該不是正確的學術名
02/07 13:20, 10F
→
02/07 13:20, 4年前 , 11F
詞，不過滿多中國選手會用的w
02/07 13:20, 11F
‣ 更多 vincent97198 的文章
文章代碼(AID): #1UEfgUDl (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 vincent97198 的文章
文章代碼(AID): #1UEfgUDl (Prob_Solve)