費瑪小定理

  • p
    是個質數,
    a
    是正整數,則
    • apa
      (mod
      p
      )
  • 證明:參考維基百科的證明:

裴蜀等式

  • 設a,b為整數,則對於方程式
    • a×x+b×y=gcd(a,b)
  • 必有整數解喔!
  • 那要如何快速求x,y呢?
  • 還記得我們怎麼求gcd嗎?輾轉相除大法!
  • 如果
    • a×x1+b×y1=gcd(a,b)
  • 有整數解,那麼
    • b×x2+(a%b)×y2=gcd(a,b)
  • 也有整數解~
  • 我們不喜歡 mod 的存在,所以換掉!
    • b×x2+(aab×b)×y2=gcd(a,b)
  • 然後整理一下
    • a×y2+b×(x2ab×y2)=gcd(a,b)
  • 得到遞迴式:
    • x1=y2
    • y1=x2ab×y2
  • 所以我們做輾轉相除法遞迴下去求x,y就好啦~
  • 當然,在最後
    a=gcd(a,b)
    b=0
    時,
    x=1,y=
    使得等式成立喔~
  • 複雜度:
    O(log(min(a,b)))
void extgcd(int a, int b, int &x1, int &y1){ if(b == 0){ x1 = 1; y1 = 0; }else{ int x2,y2; extgcd(b, a%b, x2, y2); x1 = y2; y1 = x2 - a / b * y2; } }

模逆元

  • Q:模運算我有加減乘的,有沒有除法的??
  • Q:我要電腦算
    C2000100000
    mod
    109+7
    ,但是不知道怎麼邊算邊取模
  • A:因為有除法的關係,取模的部份比較特別~
  • 假如我們要計算
    x1×y
    (mod
    M
    ),且
    M
    為質數
  • 我們希望找到一個整數
    a
    ,使得
    a×x1
    (mod
    M
    )
  • 如此一來:
    • x1×y
      (mod
      M
      )
      =
      a×y
      (mod
      M
      )
  • 所以我們只要找到整數a,便能解決這問題
  • 我們不喜歡 mod 的存在,所以在假設一個整數
    b
    • a×x+b×M=1
  • 因為
    M
    是質數,
    gcd(x,M)=1
    ,所以套入裴蜀等式就好啦!
  • BTW,我們稱呼
    a
    x
    對模數
    M
    的模逆元
  • 複雜度:
    O(log(min(a,b)))

中國剩餘定理

  • 韓信點兵問題
  • 原問題:
    n
    個人,
    n%3=2
    n%5=3
    n%7=2
    ,問
    n
    最小正整數?
  • 方法一(牛頓插值法):
    • n=a357+b35+c3+d
    • d=2,c=2,b=1,a=
      任意整數
  • 方法二(使用裴蜀定理):
    • 先合併前兩項,令
      m=a3+2=b5+3
    • a3+b(5)=1
      ,得
      a=2,b=1,m=8
    • 現在的問題變成
      n%15=8
      n%7=2
    • 再合併後兩項,令
      n=a15+8=b7+2
    • a15+b(7)=6
      ,得
      a=1,b=3,n=23
    • 得到答案
      n=23

二項式定理

(x+y)n=C0nx0yn+C1nx1yn1+C2nx2yn2+...+Cnnxny0

Ckn=n!k!(nk)!