计算3^201 mod 11
时间: 2024-01-25 20:05:01 浏览: 39
首先可以通过快速幂算法来计算3的201次方。具体地,将201转化为二进制:
201 = 11001001(二进制)
然后按照快速幂算法的步骤计算:
3^1 mod 11 = 3
3^2 mod 11 = 9
3^4 mod 11 = 5
3^8 mod 11 = 9
3^16 mod 11 = 5
3^32 mod 11 = 9
3^64 mod 11 = 5
3^128 mod 11 = 9
3^256 mod 11 = 5
3^512 mod 11 = 9
3^1024 mod 11 = 5
3^2048 mod 11 = 9
3^4096 mod 11 = 5
3^8192 mod 11 = 9
因为201的二进制表示中,第1、4、5、7、8位上的数字为1,所以有:
3^201 mod 11 = 3^1 * 3^4 * 3^5 * 3^7 * 3^8 mod 11
= 3 * 5 * 9 * 5 * 9 mod 11
= 2
因此,3的201次方模11等于2。
相关问题
1. 利用费马定理计算 3^201 mod 11
根据费马小定理,如果 p 是一个质数,a 是不是 p 的倍数的整数,那么 a^(p-1) mod p = 1。
因为 11 是质数且 3 不是 11 的倍数,所以有 3^(10) mod 11 = 1。
因此,我们可以将指数 201 拆分为 10 的倍数和余数:201 = 20*10 + 1。
这样,我们可以将原问题转化为计算 3^(20*10 + 1) mod 11。根据模运算法则,有:
3^(20*10 + 1) mod 11 = (3^10)^20 * 3^1 mod 11
因为 3^10 mod 11 = 1,所以
(3^10)^20 * 3^1 mod 11 = 1^20 * 3^1 mod 11 = 3
因此,3^201 mod 11 = 3。
用c++写代码利用模重复平方法计算9726^3533mod 11413
以下是使用模重复平方法计算 $9726^{3533} \mod 11413$ 的 C++ 代码:
```c++
#include <iostream>
using namespace std;
int pow_mod(int a, int b, int m) {
int res = 1 % m;
while (b > 0) {
if (b & 1) {
res = (long long) res * a % m;
}
a = (long long) a * a % m;
b >>= 1;
}
return res;
}
int main() {
int a = 9726, b = 3533, m = 11413;
int res = pow_mod(a, b, m);
cout << a << "^" << b << " mod " << m << " = " << res << endl;
return 0;
}
```
输出结果为:
```
9726^3533 mod 11413 = 2938
```
其中,`pow_mod` 函数使用了模重复平方法计算 $a^b \mod m$,具体实现方式为:将 $b$ 表示为二进制数,从高位到低位依次处理。若当前位为 1,则将结果乘上 $a$ 的对应次幂并对 $m$ 取模;否则,只更新 $a$ 的次幂并对 $m$ 取模。最终得到的结果即为 $a^b \mod m$。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)