A*B mod C的快速计算方法
2009-07-28 17:11:18 | 分类： 经典算法 | 标签： | 字号 大 中 小 订阅
方法一：
大家都能想到，计算A*B的值，然后在计算A*B mod C的值。这是最简单的，但是这个有个弊端，即a*b的值不能太大，太大可能溢出。
方法二：
回顾进制转换的知识，二进制转换为10进制可以以2的权值相加（貌似是这样描述的）。比如13=(1101)2=1*2^3+1*2^2+0*2^1+1*2^0。同样的，当我们计算A*B的时候，也可以将B化成2^n相加的式子。于是，我们可以将a*b mod c转换成[a*(2^b0+2^b1+……2^bn)] mod c=[a*2^b0+a*2^b1+……a*2^bn] mod c。利用公式(a+b)mod c=[(a mod c)+(b mod c)]mod c这个公式进行运算。
代码：
int mul（int a，int b，int c）
{
int result，tmp;
tmp=a%c;
while(b)
{
if(b&1) //根据2相应二进制位的值判断是否加A*2^n；因为有对b进行右移运算，所以每次只需判断最末位的结果就可以。
{
result+=tmp;
if(result>=c)
result-=c;
}
tmp<<=1; //计算 A*2^n的值。
if(tmp>=c)
tmp-=c;
b<<=1;
}
return result;
}
/*
* FZU1759.cpp
*
* Created on: 2011-10-11
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define
LL unsigned long long
LL modular_multi(LL a, LL b, LL c) {
LL res;
res =
0
;
while
(b) {
if
(b &
1
) {
res += a;
if
(res >= c) {
res -= c;
}
}
a <<=
1
;
if
(a >= c) {
a -= c;
}
b >>=
1
;
}
return
res;
}
LL modular_exp(LL a, LL b, LL c) {
LL res, temp;
res =
1
% c, temp = a % c;
while
(b) {
if
(b &
1
) {
res = modular_multi(res, temp, c);
}
temp = modular_multi(temp, temp, c);
b >>=
1
;
}
return
res;
}
int
main() {
#ifndef ONLINE_JUDGE
freopen(
"
data.in
"
,
"
r
"
, stdin);
#endif
LL a, b, c;
while
(~scanf(
"
%I64u %I64u %I64u
"
, &a, &b, &c)) {
printf(
"
%I64u\n
"
, modular_exp(a, b, c));
}
return
0
;
}
