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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
