# Math 本小節總結一些與數學（尤其是數論部分）有關的基礎，主要總結了《挑戰程序設計競賽》第二章。主要包含以下內容： 1. Greatest Common Divisor(最大公約數) 1. Prime(素數基礎理論) 1. Modulus(求模運算) 1. Fast Power(快速冪運算) ### Modulus - 求模運算 有時計算結果可能會溢出，此時往往需要對結果取余。如果有`a % m = c % m` 和 `b % m = d % m`, 那么有以下模運算成立。 - `(a + b) % m = (c + d) % m` - `(a - b) % m = (c - d) % m` - `(a × b) % m = (c × d) % m` 需要注意的是沒有除法運算，另外由于最終結果可能溢出，故需要使用更大范圍的類型來保存求模之前的結果。另外若`a`是負數時往往需要改寫為 `a % m + m`, 這樣就保證結果在`[0, m - 1]`范圍內了。 ### Fast Power - 快速冪運算 快速冪運算的核心思想為反復平方法，將冪指數表示為2的冪次的和，等價于二進制進行移位計算（不斷取冪的最低位），比如 x22=x16x4x2x^{22} = x^{16} x^4 x^2x22=x16x4x2. ### Java ~~~ import java.util.*; public class FastPow { public static long fastModPow(long x, long n, long mod) { long res = 1; while (n > 0) { // if lowest bit is 1 if ((n & 1) != 0) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } public static void main(String[] args) { if (args.length != 2 && args.length != 3) return; long x = Long.parseLong(args[0]); long n = Long.parseLong(args[1]); long mod = Long.MAX_VALUE; if (args.length == 3) { mod = Long.parseLong(args[2]); } System.out.println(fastModPow(x, n, mod)); } } ~~~