@xingxing
2017-01-15T17:07:37.000000Z
字数 1244
阅读 1192
快速幂
快速计算某个数的多少次幂,时间复杂度O(logn)
own 理解:通过把十进制幂不断除以2变为2进制位(划分幂,使得幂划分部分减少),比如(11)10=(1011)2,这样可以把高次幂的计算时间复杂度由O(n)降为O(logn)。然后由
这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情况下a*b mod c =(a mod c)*(b mod c) mod c
可以知道,通过比本位低一位的权相乘可以得到本位的权,即2^0,2^1,2^2,……,2^n,之后就要判断幂是否能划分成该位的权。可以通过二进制的最低位来判断,现在每一位都对应一个权,在不断右移二进制位时,如果该位为0即表明幂的划分中没有该位的权,如果为1,则在最后的答案上乘上该位的权,直到二进制数为0.在规定了模值的情况下,应该知道,相乘的过程是可能会溢出的,所以要根据乘数的范围,定义一个恰当的类型(一般,long long int),而且赋值也可能会溢出,所以最后取模。
不是
int n = a * a;
n = n % 1000;
而应该是
int n = a * a % 1000;
(一)快速幂位操作
#include <iostream>
#include <cstdio>
using namespace std;
//位操作
const int MOD = 100000;
long long int pow4(long long int a,long long int b)
{
long long int r = 1;
long long int base;
base = a % MOD;
while(b != 0)
{
if(b & 1) r = (r * base) % MOD;
base = (base * base) % MOD;
//printf("base = %lld\n",base);
b >>= 1;
}
return r;
}
int main()
{
long long int a,b;
while(scanf("%lld%lld",&a,&b) != EOF)
{
printf("%lld的%lld次幂为%lld\n",a,b,pow4(a,b));
}
return 0;
}
(二)快速幂
#include <iostream>
#include <cstdio>
using namespace std;
//位操作
const int MOD = 10000000;
long long int PowerMod(long long int a,long long int b)
{
long long int ans = 1;
a = a % MOD;
while(b > 0)
{
if(b % 2 == 1) ans = (ans * a) % MOD;
a = (a * a) % MOD;
b = b / 2;
//printf("a = %lld\n",a);
}
return ans;
}
int main()
{
long long int a,b;
while(scanf("%lld%lld",&a,&b) != EOF)
{
printf("%lld的%lld次幂为%lld\n",a,b,PowerMod(a,b));
}
return 0;
}