[筆記] 關於 A!/B! mod R

前幾天在競賽上碰到了一個問題的子問題：

在多次查尋下 使 單次查詢

 

複雜度達到O(1)

明顯的，是要建表、模逆表。

但模逆運算只在當模為質數時才是可行的(事實上，若模是質數，可以在O(2N)時間建完兩個表)，當模並非質數直接存表時，會發生悲劇。

因此，要設法把 A! 和 B! 提出一部分因數，使其與 R 互值。

藉由Legendre定理：

可以找出n!的p的次方數

定理相關細節可參考：Wiki

(1)建表、使用：

舉 R=pq 為例：

要建的表是：

Trivial(讀者自己想XD):

因此，便可以在O(1) 時間內取得

進而快速求得：

(2)遞推關係：

程式碼：

[待補]

建表時間大致為O(RlogR)