c加加实现快速幂算法

### 快速求余取模的实现方法 在 C++ 中，快速求余取模可以通过多种方式实现。以下是几种常见的方法及其具体实现： #### 方法一：快速幂取模 快速幂是一种高效的计算 $a^b \mod c$ 的算法，其核心思想是通过分治法减少乘法次数。这种方法的时间复杂度为 $O(\log b)$。 下面是基于递归的快速幂取模实现[^1]： ```cpp #include <iostream> using namespace std; long long pow_mod(long long a, long long b, long long c) { if (b == 0) return 1 % c; long long temp = pow_mod(a, b >> 1, c); temp = temp * temp % c; if (b & 1) temp = (temp * a) % c; return temp; } int main() { long long base = 13, exponent = 13, modulus = 10; cout << pow_mod(base, exponent, modulus); // 输出结果为 3 return 0; } ``` 此代码实现了对任意底数 `base` 和指数 `exponent` 进行快速幂取模操作，并返回最终的结果。 --- #### 方法二：迭代版快速幂取模 相比于递归版本，迭代版可以避免栈溢出的风险，在处理大规模数据时更加稳定。其实现如下[^3]： ```cpp #include <iostream> using namespace std; long long fast_pow_mod(long long a, long long b, long long c) { long long result = 1; a %= c; // 预先对底数取模 while (b > 0) { if (b & 1) result = (result * a) % c; // 如果当前位为1，则累乘到结果中 a = (a * a) % c; // 平方并取模 b >>= 1; // 移动到下一位 } return result; } int main() { long long base = 13, exponent = 13, modulus = 10; cout << fast_pow_mod(base, exponent, modulus); // 输出结果为 3 return 0; } ``` 上述代码同样能够高效完成快速幂取模的任务。 --- #### 方法三：大数取模 当面对非常大的整数（无法存储在基本数据类型中），通常会采用字符串来表示这些数字。此时的大数取模可通过逐位计算的方式解决[^2]。 以下是一个典型的例子[^4]: ```cpp #include <bits/stdc++.h> using namespace std; int big_number_mod(string num_str, int mod_val) { int remainder = 0; for(char digit : num_str){ remainder = ((remainder * 10) + (digit - '0')) % mod_val; } return remainder; } int main(){ string large_num = "12345678901234567890"; int mod_value = 1000; cout << big_number_mod(large_num, mod_value); // 输出结果为 890 return 0; } ``` 这段代码展示了如何利用字符串逐步计算一个极大数值对某个较小值的取模结果。 --- #### 性能比较与适用场景 - **快速幂取模**适用于中小规模的数据范围内的幂次运算。 - **迭代版快速幂取模**更适合于大数据量下的性能优化需求。 - **大数取模**则针对那些超出常规变量承载能力的情况提供了解决方案。 ---

在C++中，你可以编写一个函数来检查无符号整数是否为2的幂。这里是一个简单的示例： ```cpp #include <cmath> bool isPowerOfTwo(unsigned int num) { // 使用std::log2函数计算对数，如果num能被2的对数整除，说明它是2的幂 return (num > 0 && static_cast<unsigned long>(std::log2(num)) == std::log2(num)); } // 示例 int main() { unsigned int num = 16; if (isPowerOfTwo(num)) { std::cout << "Number " << num << " is a power of two." << std::endl; } else { std::cout << "Number " << num << " is not a power of two." << std::endl; } return 0; } ``` 这个`isPowerOfTwo`函数首先检查输入是否大于零，因为非正数不可能是2的幂。然后，它尝试将数字转换成`unsigned long`类型的对数，并判断结果是否等于原对数，如果相等则说明是2的幂。