快速幂取模 （位优化）

2019-04-13 14:20发布

站内文章 / 模拟电子
14964 0 1172
题目：http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=517 计算ab%k=？ （int 10位，longlong 19位） 一定不能做完指数运算再求余，因为会溢出。（去掉%k即为快速幂模板） 递归： #include #define ll long long using namespace std; ll a,b,k; ll quick(ll a,ll b,ll k){ if(b==1) return a%k; ll z=((a%k)*(a%k))%k; if(b&1){ z=(a*quick(z,b/2,k))%k; return z; } else return quick(z,b/2,k); } int main(){ while(scanf("%lld%lld%lld",&a,&b,&k)!=EOF){ printf("%lld ",quick(a,b,k)); } return 0; } 非递归： #include #include #include #include #define ll long long using namespace std; ll a,b,k; ll quick(ll x,ll n,ll k){ ll ans=1; while(n) { if(n&1)//判断n是否为奇数，若是先乘上一个 x,将其变为偶数再取余。 ans=(ans*x)%k; n>>=1;//这块是关键：：n 的值除以2，代表个数缩小一半。 x=(x*x)%k;//x变为两个x的乘积再取余。（缩短时间的关键） } return ans; } int main(){ while(scanf("%lld%lld%lld",&a,&b,&k)!=EOF){ printf("%lld ",quick(a,b,k)); } return 0; }
性质：2^3%3=(2%3)(2%3)(2%3)=2*2*2，但前两个2可以再对3取余，约简后是1*2.

热门文章