中山网站建设gdyouzi,怎么做系统软件网站,佛山市seo推广哪家好,wordpress插件储存目录为什么使用快速幂#xff1a; 假设题目要求求a的b次方。 c/c里并没有^运算符#xff0c;所以我们第一时间可能想到使用for循环#xff0c;将“a * a”语句循环b次。但是这样时间复杂度为O(n),所以当b过大的时候#xff0c;我们的程序将会非常慢#xff0c;所以我们需要使用…为什么使用快速幂 假设题目要求求a的b次方。 c/c里并没有^运算符所以我们第一时间可能想到使用for循环将“a * a”语句循环b次。但是这样时间复杂度为O(n),所以当b过大的时候我们的程序将会非常慢所以我们需要使用快速幂降低他的时间复杂度时间复杂度为O(log2n)
快速幂写法
#includebits/stdc.h
using namespace std;
#define ll long long
#define mod 998244353ll ksm(ll a, ll b)
{//a 2, b 13//2^{1101} 13841 2^8*2^4*2^1 原理位运算ll res 1;while(b){if(b1)res res * a % mod;//b1等价于b%2!0位运算依次比较b与1的二进制位a * a%mod;//2^{2^n}b 1;//b1等价于b/2位运算将b的二进制右移一位}return res%mod;
}int main()
{ll a, b;cin a b; cout ksm(a, b);return 0;
}
