#include "stdio.h" long long int fun(long long int a,long long int b) { long long int s=1; while(b) { s=s*a; b--; } return s; } main() { long long int i,n,s,sum; scanf("%lld",&n); { sum=fun(2,n); printf("%lld\n",sum); }
}
可以看到求几次方就要乘几次此时间复杂度为o（n).所以有了精进的算法快速幂。
快速幂
比如2的11次方 可以写成 2的五次方乘2的五次方乘2
如果用位运算来解释就更容易理解
比如11的二进制1011，如果用加权的方式来表示
11 = 1* 20 + 1* 21 + 0* 22 + 1* 23
可以推出2的十一次方的加权表示方法
211= 2^(1* 20) * 2^(1* 21) * 2^(1* 23)
所以可以通过位运算遇到0阶乘，遇到1则将累乘的值乘到结果。
#include "stdio.h"
long long int fun(long int a,long long int b)
{
int s=1;
while(b)
{
if(b&1) s=(s*a);
a=(a*a);
b>>=1;
}
return s;
}
main()
{ long long int i,n,s,sum;
while(scanf("%lld",&n)!=EOF)
{ s=1;
for(i=1;i<n;i++)
{
s=1;
sum=fun(2,i);
s=s+sum;
}
printf("%d\n",s);
}
}
快速幂取模
熟悉快速幂后只需理解一个数学公式ab % c = (a % c)b % c
即可写出快速幂求模
#include "stdio.h"
long long int fun(long int a,long long int b,long long int p)
{
int s=1;
while(a&&b)
{
if(b&1) s=(s*a)%p;
a=(a*a)%p;
b>>=1;
}
return s;
}
main()
{ long long int i,n,s,t=1,sum,s1,mo;
while(scanf("%lld %lld",&n,&mo)!=EOF)
{ s=1;
{
for(i=1;i<n;i++)
{
sum=fun(2,i,mo);
s=s+sum;
}
printf("%d\n",s);
}
}
}
原文：https://www.cnblogs.com/johnfllora/p/12198726.html