快速幂c 代码
时间: 2023-07-28 09:07:19 浏览: 39
下面是快速幂的 C 代码:
```c
#include <stdio.h>
long long power(long long base, long long exponent) {
long long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result = result * base;
}
base = base * base;
exponent = exponent / 2;
}
return result;
}
int main() {
long long base, exponent;
printf("Enter base and exponent: ");
scanf("%lld %lld", &base, &exponent);
printf("%lld^%lld = %lld\n", base, exponent, power(base, exponent));
return 0;
}
```
这段代码定义了一个 `power` 函数,用于计算整数的幂。其中,`base` 表示底数,`exponent` 表示指数。函数返回 `base` 的 `exponent` 次幂的值,采用了快速幂算法。在 `main` 函数中,用户输入 `base` 和 `exponent`,然后调用 `power` 函数计算结果并输出。
相关问题
斐波那契数列快速幂c语言
斐波那契数列可以用快速幂算法来进行优化,可以将时间复杂度从线性递归的 O(2^n) 降为 O(log n)。
下面是用 C 语言实现斐波那契数列快速幂的代码:
```c
#include <stdio.h>
int fibonacci(int n) {
if (n <= 1)
return n;
int a = 0, b = 1, c, i;
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
int fibonacci_fast(int n) {
if (n <= 1)
return n;
int F[2][2] = {{1, 1}, {1, 0}};
int M[2][2] = {{1, 0}, {0, 1}};
while (n > 0) {
if (n % 2 == 1) {
int tmp[2][2] = {{0, 0}, {0, 0}};
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
for (k = 0; k < 2; k++) {
tmp[i][j] += M[i][k] * F[k][j];
}
}
}
M[0][0] = tmp[0][0];
M[0][1] = tmp[0][1];
M[1][0] = tmp[1][0];
M[1][1] = tmp[1][1];
}
int tmp[2][2] = {{0, 0}, {0, 0}};
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
for (k = 0; k < 2; k++) {
tmp[i][j] += F[i][k] * F[k][j];
}
}
}
F[0][0] = tmp[0][0];
F[0][1] = tmp[0][1];
F[1][0] = tmp[1][0];
F[1][1] = tmp[1][1];
n /= 2;
}
return M[1][0];
}
int main() {
int n = 10;
printf("fibonacci(%d) = %d\n", n, fibonacci(n));
printf("fibonacci_fast(%d) = %d\n", n, fibonacci_fast(n));
return 0;
}
```
其中 `fibonacci` 函数是用线性递归的方式计算斐波那契数列的值,而 `fibonacci_fast` 函数则是用快速幂算法来计算斐波那契数列的值。
模幂运算的快速算法c语言代码
以下是快速幂算法的C语言代码:
```
int FastExponentiation(int base, int exponent, int mod) {
int result = 1;
base %= mod;
while (exponent > 0) {
if (exponent & 1) {
result = (result * base) % mod;
}
exponent = exponent >> 1;
base = (base * base) % mod;
}
return result;
}
```
其中,base表示底数,exponent表示指数,mod表示取模数。这段代码通过位运算的方法快速计算出整数的幂次方,并对mod取余以避免数值溢出等问题。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)