数论

辗转相除法

// 欧几里得算法（迭代版本）
int gcd_euclidean_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

gcd最大公约数

费马小定理

如果 p 是一个质数（Prime Number），而整数 a 不是 p 的倍数（即 a 与 p 互质），那么：

快速幂

#define llong long long
const llong ESP = 1e9+7;
llong power(llong num,llong d){
    llong re = 1 % ESP;
    llong base = num % ESP;
    while(d > 0){
        if(d % 2 == 1){
            re = re * base % ESP;
        }
        base = base * base % ESP;
        d /= 2;
    }
    return re;
}