PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Prob_Solve
[問題] 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
繼續閱讀
Re: [問題] 關於擴展歐幾里得算法
LPH66
[問題] 關於擴展歐幾里得算法
nevikw39
[問題] 機率的問題
bagafuok
[問題] 01背包的暴搜有甚麼特別的剪枝嗎?
s89162504
[問題] Leetcode 294 Flip Game II
wheels
Fw: [問題] 使用bit來篩檢質數
wa007123456
[問題] Knapsack problem
cloud2000s
[問題] 演算法問題
cloud2000s
[問題] APCS 20191026 P4
fatcat8127
[問題] 高中數學請問
wozmirror
Links
booklink
Contact Us: admin [ a t ] ucptt.com