信息学奥赛一本通（1326：【例7.5】 取余运算（mod））

1326：【例7.5】 取余运算（mod）

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 10443     通过数: 4787

【题目描述】

输入b，p，k的值，求b^p mod k的值。其中b，p，k×k为长整型数。

【输入】

输入b，p，k的值。

【输出】

求b^p mod k的值。

【输入样例】

2 10 9

【输出样例】

2^10 mod 9=7

【分析】

        本题主要的难点在于数据规模很大（b、p都是长整型数），对于 b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。

        下面先介绍一个原理∶a*b%k=（a%k）*（b%k）%k。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？显然对于任何一个自然数p，有p=2*p/2+p%2，如 19=2 * 19/2＋19%2=2*9＋1，利用上述原理就可以把b的 19次方除以 k 的余数转换为求b的9次方除以k 的余数，即 b^19=b^(2*9+1)=b*b^9*b^9，再进一步分解下去就不难求得整个问题的解。

【参考代码】

#include <stdio.h> int b,p,k; int f(int p) //利用分治求 b^p%k {int tmp;if(p==0) // b^p%k=1return 1;tmp=f(p/2)%k;tmp=(tmp* tmp)%k; // b^p%k=(b^(p/2))^2%kif(p%2==1)tmp=(tmp*b)%k; //如果p为奇数，则 b^p%k=(b^(p/2))^2)*b%kreturn tmp; } int main() {int tmpb;scanf("%d%d%d",&b,&p,&k);tmpb=b; //将b的值备份b%=k; //防止 b太大printf("%d^%d mod %d=%d\n",tmpb,p,k,f(p)); //输出return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1326

总结

以上是生活随笔为你收集整理的信息学奥赛一本通（1326：【例7.5】 取余运算（mod））的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。