快速幂算法：优化时间复杂度到O(log p) | C++实现

将时间复杂度缩小到O(1)是不可能的。因为在这个代码中，我们需要对每个数i进行幂运算fast_pow(i, p - 2, p)，这个幂运算的时间复杂度是O(log p)。所以整个代码的时间复杂度是O(n * log p)。无论n和p的值如何，这个时间复杂度都无法缩小到O(1)。\n\n但是，我们可以通过优化幂运算来提高效率。快速幂算法可以将求幂运算的时间复杂度从O(p)优化到O(log p)。\n\n以下是用C++实现的快速幂算法：\n\ncpp\n#include <iostream>\n\nlong long fast_pow(long long base, long long exponent, long long mod) {\n long long result = 1;\n while (exponent > 0) {\n if (exponent % 2 == 1) {\n result = (result * base) % mod;\n }\n base = (base * base) % mod;\n exponent /= 2;\n }\n return result;\n}\n\nint main() {\n int n, p;\n std::cin >> n >> p;\n \n for (int i = 1; i <= n; ++i) {\n std::cout << fast_pow(i, p - 2, p) << "\n";\n }\n \n return 0;\n}\n\n\n快速幂算法原理\n\n快速幂算法的核心思想是将指数进行二进制分解，然后利用递归的思想来计算幂运算。例如，求2^10，可以将10分解成二进制形式：1010。则2^10 = 2^(2^3 + 2^1) = 2^(2^3) * 2^(2^1) = 2^8 * 2^2。\n\n代码解析\n\n代码中，fast_pow函数实现了快速幂算法。函数参数分别为底数base、指数exponent、模数mod。\n\n函数循环遍历指数的二进制位，如果当前位为1，则将结果乘以当前的底数，并将底数平方。\n\n总结\n\n快速幂算法是一种非常高效的求幂算法，可以将时间复杂度从O(p)优化到O(log p)，大幅提高计算效率。在实际应用中，快速幂算法经常被用于密码学、大数计算等领域。