有机生态农业网站模板,德阳高端网站建设,网站做seo必要的结构,wordpress主题momo利用乘法求解次幂问题—快速幂 50. Pow(x, n)372. 超级次方 50. Pow(x, n)
题目链接#xff1a;50. Pow(x, n) 题目内容#xff1a; 题目就是要求我们去实现计算x的n次方的功能函数#xff0c;类似c的power()函数。但是我们不能使用power()函数直接得到答案#xff0c;那… 利用乘法求解次幂问题—快速幂 50. Pow(x, n)372. 超级次方 50. Pow(x, n)
题目链接50. Pow(x, n) 题目内容 题目就是要求我们去实现计算x的n次方的功能函数类似c的power()函数。但是我们不能使用power()函数直接得到答案那样这道题就失去了考察的意义。 前面提到乘法a*b可以看作是b个a相加用加法来完成乘法x的n次方就是n个x相乘那么同样可以用乘法来代替次幂计算我们称之为快速幂。比如5^7就是7个5相乘快速幂的过程如下 第一轮是乘以5第二轮乘以5*5第三轮乘以(5*5)*(5*5)也就是每一轮乘的数都在加倍这样就能够在log^n的时间复杂度内完成x^n的计算。代码实现如下C class Solution {
public:double myPow(double x, int n) {//先处理特殊情况if(x 0) return 0.0;if(x 1) return 1.0;if(n 0) return 1.0;bool flage false;long _n n;//如果n是负数x^n 1/(x^|n|)if(_n 0){flage true;_n -_n;}double ans 1;double mul x;//快速幂主体过程while(_n){ if(_n1) //如果n末位为1就乘以mulans * mul; mul * mul; //mul翻倍_n 1; //n右移一位}return flage ? 1.0/ans : ans; //判断是否需要变成倒数}
};372. 超级次方
题目链接372. 超级次方 题目内容 看起来和上一题是差不多的但是由于b是一个非常大的正整数以数组形式给出[1,0,3,4]就表示1034【末位是个位然后是十位然后是百位最前面的是最高位】。其中1 b.length 2000说明b可以达到10^1999的程度根本没法用double、long long等数据类型来存储这么大的数所以在运算过程中也不能直接把b转换成一个数或者每一位转换成一个数需要其他方法 将每一位b[i]的数值b[i]*10^(m-1-i)【其中m是b.length】分解成b[i]和10^(m-1-i)两部分每次先求a^(10^(m-1-i))得到A再求A^b[i]。a^(10^(m-1-i))随着i的减小越来越大但是可以看作是上一轮的A^10。 由于每次次幂结果都要mod 1337所以结果是不会溢出的a^(10^(m-1-i))每一次用上一轮的A^10来表示就解决了b很大的问题。另外需要注意的是(a*b) mod k ( (a mod k) * (b mod k) ) mod k。 a^(10^(m-1-i))和A^b[i]以及A^10都用快速幂求解。快速幂过程中根据(a*b) mod k ( (a mod k) * (b mod k) ) mod k加上求模操作。代码如下C
class Solution {
public://快速幂long quick_pow(int a, int n){int ans 1;int mul a;while(n){if(n1)//加上求模操作ans ( (ans % 1337) * (mul % 1337)) % 1337;//mul也加上求模操作mul ((mul % 1337) * (mul % 1337)) % 1337;n1;}return ans;}int superPow(int a, vectorint b) {int ans 1; for(int j b.size() - 1; j 0; j--){ans ( (ans % 1337) * (quick_pow(a,b[j]) % 1337) ) % 1337;//每次a都在上一次的基础上变成其10次方a quick_pow(a, 10);}return ans;}
};
