C++快速冪與大數(shù)取模算法示例
更新時間：2016年08月29日 11:15:18 投稿：daisy
這篇文章主要介紹了C++快速冪算法和大數(shù)取模算法的示例，對C++程序員來說有一定的幫助，有需要的朋友可以參考借鑒，下面來一起看看。
一、快速冪
其實(shí)就是求（a^b）% p ,（其中a,b,p都比較大在int范圍內(nèi)）這類問題。
首先要知道取余的公式： （a*b）%p=（a%p*b%p）%p 。
那么冪不就是乘機(jī)的累積嗎，由此給出代碼：
int fast(int a,int b,int p)
{ long long a1=a,t=1;
while(b>0)
{ if(b&1) /如果冪b是奇數(shù)多乘一次，因為后邊會除2變偶數(shù)，（7/2=3）
t=(t%p)*(a1%p)%p;
a1=(a1%p)*(a1%p)%p;
b/=2; }
return (int)(t%p);
}
二、大數(shù)取模
它的原理就是這個取余公式： （a+b）%p=(a%p+b%p)%p;
那么大數(shù)可以看做每一位的那位數(shù)字乘以自身的權(quán)然后每位相加。
如：12345678=（1*10000000）+（2*1000000）+…+8。
代碼如下：
char s[200];
#define mod 10000010;
int main()
{ while(gets(s))
{ int k=strlen(s),sum=0;
for(int i=0;i<k;i++)
sum=(sum*10+s[i]-'0')%mod; /當(dāng)然要是擔(dān)心sum還可能溢出，那就對里邊再拆開來取余
cout<<sum<<endl;
} }
三、總結(jié)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)和工作能有所幫助。如果有疑問可以留言交流。
您可能感興趣的文章:
相關(guān)文章
關(guān)于C++11的統(tǒng)一初始化語法示例詳解
C++之前的初始化語法很亂，有四種初始化方式，而且每種之前甚至不能相互轉(zhuǎn)換，但從C++11出現(xiàn)后就好了，所以這篇文章主要給大家介紹了關(guān)于C++11的統(tǒng)一初始化語法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下。2017-10-10
C++實(shí)現(xiàn)LeetCode(132.拆分回文串之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(132.拆分回文串之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)控制臺版的掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了深入理解C++編程中的局部變量和全局變量,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
std::shuffle是C++標(biāo)準(zhǔn)庫中的一個函數(shù),用于對容器中的元素進(jìn)行隨機(jī)排列,本文主要介紹了C++中std::shuffle的使用小結(jié),具有一定的參考價值,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了C語言遞歸實(shí)現(xiàn)字符串逆序的方式詳解,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-10-10
C++編程中將引用類型作為函數(shù)參數(shù)的方法指南
這篇文章主要介紹了C++編程中將引用類型作為函數(shù)參數(shù)的方法指南,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
C++ 智能指針使用不當(dāng)導(dǎo)致內(nèi)存泄漏問題解析
這篇文章主要介紹了C++ 智能指針使用不當(dāng)導(dǎo)致內(nèi)存泄漏問題解析,本文通過代碼示例給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-07-07
這篇文章主要給大家介紹了關(guān)于C/C++語言中全局變量重復(fù)定義問題的解決方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-01-01
這篇文章主要介紹了Qt在vs2019中使用及設(shè)置方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08