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

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

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

【题目描述】

【输入】

【输出】

【输入样例】

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=1
		return 1;
	
	tmp=f(p/2)%k;
	tmp=(tmp* tmp)%k;   // b^p%k=(b^(p/2))^2%k
	if(p%2==1)
		tmp=(tmp*b)%k;	//如果p为奇数，则 b^p%k=(b^(p/2))^2)*b%k
	return 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