快速冪與快速乘法

?

---

List

• 快速冪與快速乘法
  • List
  • Knowledge
  • 快速冪
    • 原理
    • code
  • 快速乘法
    • 原理
    • code

Knowledge

快速冪

原理

a^b%p
采用二進制得思想，將b轉化為二進制數。
b = c0×2^0+c1×2^1+c2×2^2+c3×2^3+……cn×2^n
a^b = a^(a1×2^0)×a^(c1×2^1)×……×a^(cn×2^n)
所以我們可以在log(b)的時間內求出a^(2^0)，a^(2^1)……a^(2^n)同時c也可得到，故復雜度O(log(b))
eg.a^11
11的二進制是1011
11 = 23×1 + 22×0 + 21×1 + 2o×1

code

int quick_pow(int a,int b,int p){int w=1;while(b){if(b&1)w=(w*a)%p;b>>=1;a=(a*a)%p;}return w;
}

?

快速乘法

原理

a*b%p
與快速冪類似
a*b=a*(c0×2^0+c1×2^1+c2×2^2+c3×2^3+……cn×2^n)
在log(b)的時間內可以求出a*2^i

code

int quick_mul(int a,int b,int p){int w=0;while(b){if(b&1)w=(w+a)%p;b>>=1;a=(a+a)%p;}return w;
}

?