洛谷 P1226 【模板】快速幂||取余运算

给你三个整数 b,p,kb,p,k，求 b^p \bmod kbpmodk。

一行三个整数 b,p,kb,p,k

输出 b^p mod k=s

ss 为运算结果

【样例解释】
2^{10} = 1024210=1024，1024 \bmod 9 = 71024mod9=7。

【数据范围】
对于 100\%100% 的数据，0\le b,p,k < 2^{31}0≤b,p,k<231。

代码

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd; int ksm(int b,int p,int k) { int sum; if(b==0&&p!=0) return0; if(b==0&&p==0) return0; if(b!=0&&p==0) return1; sum=ksm(b,p>>1,k); sum=1ll*sum*sum%k; if(p%2==1) sum=1ll*sum*b%k; return sum; } int main(void) { longlong b,p,k,s; cin>>b>>p>>k; cout<<b<<"^"<<p<<" mod "<<k<<"="<<ksm(b,p,k)%k; return0; }

一个数a的n次方可能会很大，在计算过程中，虽然可以运用取模运算将a的某次幂保留在模p的范围内，但下一次的运算就有可能爆（a<=10^9；b<=10^9;c=a*b<=10^18);

故在运算过程中，可以将a的指数k不断二分，这样，可以使它的幂分成两个较小幂的形式，在转化为long long 类型数据，可以有效防止运算结果过大。