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

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视频精品免费视频免里 | 亚洲水蜜桃久久综合网站 | 亚洲美女在线播放 | 四虎免费影视 | 大ji吧快给我别停受不了视频 | 日本人成年视频在线观看 | 国产欧美日韩网站 | 久久精品国产亚洲妲己影院 | 亚洲精品成人网 | 伊人久久99亚洲精品久久频 | 99久久国产综合精品女不卡 | 久久99精品国产麻豆宅宅 | 亚洲第一黄色网址 | 久久一区二区精品综合 | 久久青草免费91线频观看站街 | 97色在线观看 | 2021久久精品永久免费 | 五月婷婷在线观看 | 亚洲成人伊人网 | 欧美亚洲欧美 | 成人影院高清在线观看免费网站 | 国产精品香蕉在线观看不卡 | 视色视频在线 | 四虎影院在线播放视频 | 国产日产精品久久久久快鸭 | 精品亚洲视频在线 | 免费在线观看黄色的网站 | 中文字幕专区高清在线观看 | 国产精品免费视频一区 | 一日本道加勒比高清一二三 | 天天曰夜夜操 | 在线日韩观看 | 波多野结衣免费播放 | 国产精品线在线精品国语 | 亚洲天天做日日做天天欢毛片 |