C语言快速幂取模算法小结

快速幂算法是用来加速计算 a^n 的算法，它可以使计算复杂度从O(n)降为O(logn)，因此在需要对 a^n 进行大量计算时非常有用。而在取模运算中，快速幂算法同样适用，因为我们可以在计算时对中间结果进行模运算的操作，这样可以避免数值溢出。

算法说明

快速幂取模算法的实现中主要有以下几个步骤：

1. 如果n等于0，直接返回1。
2. 如果n为偶数，计算 a^(n/2)，并将结果记为 x，那么 a^n = x*x。
3. 如果n为奇数，计算 a^(n-1)，并将结果记为 x，那么 a^n = x*a。
4. 对 a^n 进行模运算，将结果返回。

算法示例1 - 计算a^b mod p

下面是一个计算 a^b mod p 的示例，其中a和b为整数，p为一个质数。

long long power_mod(long long a, long long b, long long p) {
    long long ans = 1;
    a = a % p;
    while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * a) % p;
        }
        b = b / 2;
        a = (a * a) % p;
    }
    return ans;
}

在该函数中，我们首先对 a 进行了取模操作，以避免在计算时数值过大导致的溢出问题。然后通过下面的循环来进行快速幂计算：

while (b > 0) {
        if (b % 2 == 1) {
            ans = (ans * a) % p;
        }
        b = b / 2;
        a = (a * a) % p;
    }

其中，如果 b 为奇数，我们将结果与 ans 相乘，然后再对其进行取模操作。如果 b 为偶数，我们直接将 a 平方，并将 b 除以2。这样就能够将计算复杂度降低到log级别。

算法示例2 - 计算Fibonacci数列的第n项

下面是一个计算Fibonacci数列的第n项的示例代码，其中n为一个非负整数。

long long fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    long long a = 1, b = 1, c = 0;
    for (int i = 3; i <= n; i++) {
        c = (a + b) % 1000000007;
        a = b;
        b = c;
    }
    return c;
}

在该函数中，我们使用了一个循环来逐步计算 Fibonacci 数列的第n项。在计算中，我们利用快速幂取模算法进行了模运算的操作，以避免在计算时数值过大导致的溢出问题。

总结

快速幂取模算法是一种简单而有效的算法，在处理大量幂运算和模运算的问题时非常有用。在实现中需要注意数值的取模以避免溢出问题。