洛谷  取余运算||快速幂 1226

其实比起楼下的大佬们，我主要是多了些位运算和讲解。

想法一：

直接输出 pow(b,q)%k

嗯~~勇气可嘉，但是看一眼数据范围（长整型）就会意识到，这个方法也许一个点都过不了。

想法二：

while(q2--) ans=ans*b%k;

用代码说话吧（简单、粗暴、易懂），意想不到的是只有一个点没过。

快速幂

在每一次进行循环时，如果q为奇数，则b^q可以转为b^2的q/2次方乘以b。所以每一次进行b^2计算时，需要根据q是否为奇数决定是否在最终的结果上乘以b。

时间复杂度O(logn)，完爆数据。

#include
      
       using namespace std;long long b,b2,q,k,cur,ans=1;int main(){    scanf("%lld%lld%lld",&b,&q,&k);    cur=q;    b2=b;    while(cur)    {        if(cur&1) ans=ans*b2%k;        cur>>=1;        b2=b2*b2%k;    }    printf("%lld^%lld mod %lld=%lld",b,q,k,ans%k);    return 0;}