#include<bits/stdc++.h> #include <functional> using namespace std; long long power(long long a,long long b,long long c){ if(b0){ return 1; } int t=power(a,b/2,c); t=(long long)t*t%c; if(b%21){ t=(long long)t*a%c; } return t; } int main(){ long long a,b,c; cin>>a>>b>>c; cout<<a<<"^"<<b<<" "<<"mod"<<" "<<c<<"="<<power(a,b,c); }

递归 时间复杂度：O(log2k)O(log_2k)O(log2 k)

不要暴力，别问我为什么

时间复杂度:O(log2k)时间复杂度: O(log_{2} k) 时间复杂度:O(log2 k)

cpp代码解释1. 快速幂取模函数 mod:•这个函数使用了快速幂算法，可以在对数时间内计算 ( a^b \mod p )。•a = a % p 为了防止 a 太大，先取模。•使用位运算来判断 b 是否为奇数，并进行相应的乘法和取模操作。•每次将 b 右移一位（相当于除以 2），并将 a 平方后取模。2. 主函数 main:•从标准输入读取三个整数 a, b, p。•调用 mod 函数计算 ( a^b \mod p ) 的结果。•输出结果，格式为 a^b mod p=result。示例运行对于输入 2 10 9，程序的输出将是：2^10 mod 9=7

C++ py

快速幂

事实上，Python自带快速幂 所以我们的AC代码就是