# 基礎數論 by: hush --- 先偷教一個小技巧「**快速冪**」 ---- 計算$a^n=\overbrace{a\times a\times ...\times a}^\text{n項}$，時間複雜度$O(n)$ 太慢了！ ---- 若將$n$換成二進制表示也就是$n_{(10)}=k_0k_1...k_{c(2)}=k_02^c+k_12^{c-1}+...+k_c2^0$ 例如： $23_{(10)}=10111(2)=1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+1\cdot 2^0$ ---- 就可以把$a^{23}=a^{2^4+2^2+2^1+2^0}=a^{2^0}\times a^{2^1}\times a^{2^2}\times a^{2^4}$ 顯然2的次方加一就平方一次，搭配短除法剛好可以求二進制倒過來的數列，就能在$O(log\ n)$內求解 通常會搭配取餘數(等等會教) ---- code ```cpp= int fastpower(int a,int n,int m) { //要對m取餘數 int ans=1; a%=m; while (n>0) { if (n%2==1) ans=(ans*a)%m; a=(a*a)%m; n/=2; } return ans; } ``` ---- 練習題 - [CSDC99](https://csdc.tw/problem/99/) ---- AC code ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; int fp(int a,int b,int p) { int ans=1; for (a%=p; b; b>>=1,a=(a*a)%p) if (b&1) ans=(ans*a)%p; return ans; } signed main() { int t,a,b; cin >> t; while (t--) { cin >> b >> a; cout << fp(a,b,1e9+7) << '\n'; } } ``` --- ## 符號介紹 ---- - 屬於符號：$a\in S，表示a在S集合裡$ - 因數符號：$a\mid b，a是b的因數$ - 最大公因數：$\gcd(a,b)或是(a,b)$ - 最小公倍數：$\operatorname{lcm}(a,b)或是[a,b]$ - 取模符號：$a\bmod b，表示a除b得到的餘數$ - 同餘符號：$a\equiv b\pmod m，表示a,b模m的餘數相等$ --- ## 模運算 ---- 可作除了除法外的四則運算 以下介紹較常用的運算性質 - 加(減)法有分配律： $(a\pm b)\bmod m\equiv a\bmod m\pm b\bmod m$ - 乘法有分配律： $(a\times b)\bmod m\equiv a\bmod m\times b\bmod m$ - 除法要用乘法逆元 ---- 如果題目中看到類似：「因為答案可能很大請對$10^9+7$取餘數」這種敘述就不用怕，每次加減乘的時候都取模一次即可(減法要小心出現負數) ---- ### 費馬小定理 ---- ## when $p$ is a prime ## $a^{p-1}\equiv 1\pmod p$ ---- - proof： 完全剩餘系+乘法分配律 ---- - 練習題： 計算$a^{b^c}\bmod p，其中p為質數(a,b,c\le 10^{18})$ ---- ### 模逆元 - 又稱乘法逆元，就是抵銷乘法的元素(除法) 我們定義$a$的模逆元為$a^{-1}$也就是 $k\cdot a\cdot a^{-1}\equiv k\pmod m$ - 求模逆元(模質數時)： $\because a^{p-1}\equiv 1\pmod p$ $\therefore a^{p-2}\equiv a^{-1}\pmod p$ (記得要快速冪) ---- 有了模逆元要計算$\div a$就可以用$\times a^{-1}$來算 - 例如可用來計算$\mathrm{C}^m_n\bmod p=\frac{m!}{n!(m-n)!}\bmod p$ ---- 練習題 - [ZJ a157](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a157) ---- AC code ```cpp= #include<bits/stdc++.h> #define int long long using namespace std; int fp(int a,int b,int p) { int ans=1; for (; b; b>>=1,a=(a*a)%p) if (b&1) ans=(ans*a)%p; return ans; } signed main() { int n,p; cin >> n >> p; while (n--) { int k; cin >> k; cout << fp(k,p-2,p) << " \n"[!n]; } } ``` --- # 謝謝大家