1.最大公约数

$gcd(a,b) = a, {if}\ b=0$

$gcd(a,b) = gcd(b,a\%b), {if}\ b\neq 0$

2.快速幂

$f(n) = a^n \% c$

龟速法：

那么 $n=0$ 时， $f(n)=1\%c$

$n \neq 0$ 时， $f(n)=f(n-1)*a \%c$

快速法：

那么 $n=0$ 时， $f(n)=1\%c$

$n$ 为偶数时，$f(n) = f^2(n/2) \% c$

$n$ 为奇数时，$f(n) = f(n-1) * a \%c$