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

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條評論
主站蜘蛛池模板: 久久精品久噜噜噜久久 | 精品毛片 | 久久精品国产曰本波多野结衣 | 欧美三级美国一级 | 国内精品综合九九久久精品 | 在线免费观看一区二区三区 | 老司机午夜性大片免费 | 米奇精品一区二区三区在线观看 | 成年女人免费毛片视频永久 | 亚欧精品一区二区三区 | 爽爽影院免费观看视频 | 欧美一级毛片特黄大 | 久青草视频免费视频播放线路1 | 久久是精品 | 国产成人一区二区视频在线观看 | 91美女啪啪 | 亚洲精品乱码国产精品乱码 | 亚洲国产精品久久久久婷婷软件 | 综合网天天操天天射 | 欧美专区综合 | 久久综合给合久久97色美利坚 | 青青国产成人久久91网 | 91精品国产免费久久久久久青草 | 在线色国产 | 久草免费公开视频 | 另类图片综合网 | 久久99国产精品免费观看 | 免费在线观看的毛片 | 四虎国产成人免费观看 | 欧美乱大交xxxxx在线观看 | 国产欧美国产精品第一区 | 免费超级淫片日本高清视频 | 亚洲性一级理论片在线观看 | 午夜在线播放 | 午夜伦y4480影院中文字幕 | 欧美成在线视频 | 99r在线精品 | 一级特级aa欧美毛片 | 欧美日韩一区二区三区自拍 | 国产在线麻豆精品 | 老子午夜精品我不卡影院 |