亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

fzu 1752 A^B mod C fzu 1650 AB mod C

系統 1685 0


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 ;
}



fzu 1752 A^B mod C fzu 1650 AB mod C


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久99精品国产99久久6男男 | 久久影院中文字幕 | 天天综合天天添夜夜添狠狠添 | 国产日产精品久久久久快鸭 | 日韩高清中文字幕 | 精品国产一级毛片大全 | 久草视频中文 | 欧美一级毛片免费高清aa | 久久精品国产日本波多麻结衣 | 免费h片网站 | 色狠狠xx| 大ji吧快给我别停受不了视频 | 精品国产免费久久久久久婷婷 | 久久久久久久一线毛片 | 成人精品视频一区二区在线 | 久久午夜夜伦伦鲁鲁片 | 国产精品人成福利视频 | 99热在线这里只有精品 | 99综合| 久久久久毛片免费观看 | 欧美在线成人午夜影视 | 免费一级毛片在线播放欧美 | 国产精品久久久久免费视频 | 天天综合色天天综合网 | 欧美成人在线免费 | 99久久国产综合精品成人影院 | 久久婷婷激情综合中文字幕 | 精品在线一区二区三区 | 国产性一交一乱一伦一色一情 | 99热久久这里只精品国产ww | 春暖花开亚洲 | 伊人365影院| 狠狠狠狠狠狠狠狠 | 国产精品国偷自产在线 | 亚洲一区二区欧美 | www.日日| 久久日本经典片免费看 | 日本老太做爰xx | 亭亭色| jizz中国zz女人18 | 曰曰啪天天拍视频在线 |