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

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條評論
主站蜘蛛池模板: 久草视频大全 | 国产精品柳州莫菁身材四 | 日本免费小视频 | 香蕉视频网站在线播放 | 久久国产亚洲 | 天天狠狠色综合图片区 | 国产一级α片 | 国产成人精品亚洲777图片 | 国产日比视频 | 亚洲成人在线视频播放 | 高清视频在线播放 | 91精品推荐 | 一二三区在线观看 | 国产一区在线免费观看 | 国产边打电话边被躁视频 | 国产成人精品无缓存在线播放 | 国产真实一区二区三区 | 欧亚在线视频 | 波多野结衣在线一区二区 | 波多野结衣一二三区 | 亚洲免费福利视频 | 看福利影院 | 欧美精品aaa久久久影院 | 成人观看视频 | 99久久99久久精品国产 | 久久久久久99精品 | 青草青在线免费视频 | 日本高清不卡一区久久精品 | 亚洲欧美日韩综合 | 亚洲精品96欧美一区二区 | 免费观看国产网址你懂的 | 99国产精品一区二区 | 亚洲va高清中文字幕 | 精品麻豆 | 国产一区中文字幕 | 国产一区二区福利久久 | 天天综合天天射 | 国产精品久久二区三区色裕 | 国产精品久久久久影院色老大 | 国产永久| 奇米777四色影视在线看 |