[心得] Codeforces 603B
看板Prob_Solve (計算數學 Problem Solving)作者rareone (拍玄)時間5年前 (2019/03/26 13:29)推噓1(1推 0噓 5→)留言6則, 2人參與討論串1/1
最近在刷些題，所以如果寫題目有些感想會在這邊多發點寫題心得，順便賺點批幣
題幹：印出有幾個從 {0,.., p - 1} 打到自己的函數 f （不一定是排列），使得
f(k * x mod p) = k * f(x) mod p
作法：
因為 (Z_p \ {0}, *) 跟 (Z_{p - 1}, +) 同構，可以把 *k 這個操作會生出一些 cycle 分別是
1 -> k -> k^2 -> .. -> 1
印此每個 cycle 大概長這樣
a -> a * k -> a * k^2 -> .. -> 1 -> a
特別地，0 自成一個cycle
每個 cycle 可以抓出一個元素來 represent
寫作 0, a_1, a_2, a_3, .., a_n
讓每個代表打到 {0, .., p - 1} 可以唯一決定一個函數，構造方法就如給定規則
這題其實可以做到跟分解 p - 1 速度一樣快，方法是
寫作 p - 1 = \prod_i q_i^{r_i}
對於每個 r_i 逐一測試最小的 t_i 使得 0 <= t_i <= r_i 且
a^{q_i^{t_i} \prod_{j != i} q_j^{r_j} = 1
那麼 k 的 ord 就是 a^{\prod_i q_i^{t_i}} cycle 數量就是 (p - 1) / ord
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.40.187
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1553578193.A.331.html
推
03/26 23:18,
5年前
, 1F
03/26 23:18, 1F
→
03/27 01:41,
5年前
, 2F
03/27 01:41, 2F
→
03/27 01:41,
5年前
, 3F
03/27 01:41, 3F
→
03/27 01:41,
5年前
, 4F
03/27 01:41, 4F
→
03/27 01:42,
5年前
, 5F
03/27 01:42, 5F
→
03/27 01:43,
5年前
, 6F
03/27 01:43, 6F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
