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
;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
