锐客网

  1. 首页 > it技术 > >

快速幂和取余运算

将指数转换为2进制，如2的11次方，11的二进制为1011，即8+2+1，所以通过下图base的自增和具体位的0或者1来给ans加base。这样时间复杂度为O(n)=log(2)(n)，效率很高。

  1. 题目来源洛谷:P1226 【模板】快速幂||取余运算
实现代码如下:
#include #include using namespace std; int main() { int a, b; scanf("%d%d",&a,&b); int base=a,ans=1; //赋初值 while(b>0) { if(b&1)//按位与0001，只有最右边同为1才执行 { ans*=base; } base*=base; //base自增 b>>=1; //b右移，这样可以一直判断最右边那一位 } cout<

模运算有以下性质
(A+B) mod b=(A mod b+B mod b) mod b
(A×B) mod b ==((A mod b)×(B mod b)) mod b
所以
代码如下
#include #include using namespace std; int main() { long long a, b,k; scanf("%lld%lld%lld",&a,&b,&k); if(a==k)//特判，如1 0 1 { printf("%lld^%lld mod %lld=0",a,b,k); return 0; } long long t=b; //将b的值保存下来用来输出 long long base=a,ans=1; //赋初值 while(t>0) { if(t&1)//按位与0001，只有最右边同为1才执行 { ans*=base; ans%=k; } cout<>=1; //b右移，这样可以一直判断最右边那一位 } printf("%lld^%lld mod %lld=%lld",a,b,k,ans); return 0; }

  1. 题目来源洛谷P1010 幂次方
    看到这道题的递归题解心中万分震惊，原来可以这么简单，递归nb！话不多说，上代码。
#include using namespace std; string fun(int t,int i=0,string s=""); int main() { int n; cin>>n; cout<>=1; i++; //次数+1 }; return s; }

【快速幂和取余运算】↓更简洁的快速幂代码如下
do { if(t&1) { s=(i==1?"2":"2("+fun(i)+")")+(s==""?"":"+")+s; } }while(i++,t>>=1);

    推荐阅读


    上一篇：孩子犯错后，父母的态度将决定孩子会成为什么样的人。

    下一篇：2018年8月23|2018年8月23 日