?

次方求模

時(shí)間限制：1000 ms ?|? 內(nèi)存限制：65535 KB 難度：3 描述

求a的b次方對c取余的值

?

輸入

第一行輸入一個(gè)整數(shù)n表示測試數(shù)據(jù)的組數(shù)（n<100）
每組測試只有一行，其中有三個(gè)正整數(shù)a,b,c(1=<a,b,c<=1000000000)

輸出

輸出a的b次方對c取余之后的結(jié)果

樣例輸入

3 2 3 5 3 100 10 11 12345 12345

樣例輸出

3 1 10481

來源

[張?jiān)坡擼原創(chuàng)

上傳者

張?jiān)坡?/dd>

#include<stdio.h> long long fun(long long a,long long b,long long c) {long long r=a%c;long long k=1;while(b){if (b&1)k=(k*r)%c;r=(r*r)%c;b>>=1;}return k; } int main() {int n;scanf("%d",&n);while(n--){long a,b,c,count;scanf("%d %d %d",&a,&b,&c);count=fun(a,b,c);printf("%d\n",count);}return 0; }

看著代碼很簡單，可是背后蘊(yùn)含了多少了汗水啊！看一下算法吧：其實(shí)就是a^29=a^14*a,而a^14=a^7*a^7,a^7=a^3*a^3,a^3=a^2*a,這樣求a^29就用了7次乘法，不知你有沒有發(fā)現(xiàn)，這和二分法查找很相似，每次規(guī)模都近視減少了一半。注意long long 的使用，否則就會溢出，得不到正確答案。

補(bǔ)充：

利用模運(yùn)算的運(yùn)算規(guī)則，我們可以使某些計(jì)算得到簡化。例如，我們想知道3333^5555的末位是什么。很明顯不可能直接把3333^5555的結(jié)果計(jì)算出來，那樣太大了。但我們想要確定的是3333^5555（%10），所以問題就簡化了。 根據(jù)運(yùn)算規(guī)則（4）a^b% p = ((a % p)^b) % p ，我們知道3333^5555（%10）= 3^5555（%10）。由于3^4 = 81，所以3^4（%10）= 1。 根據(jù)運(yùn)算規(guī)則（3） (a * b) % p = (a % p * b % p) % p ，由于5555 = 4 * 1388 + 3，我們得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10） =（1 * 7）（%10）= 7。 計(jì)算完畢。 利用這些規(guī)則我們可以有效地計(jì)算X^N(% P)。簡單的算法是將result初始化為1，然后重復(fù)將result乘以X，每次乘法之后應(yīng)用%運(yùn)算符（這樣使得result的值變小，以免溢出），執(zhí)行N次相乘后，result就是我們要找的答案。 這樣對于較小的N值來說，實(shí)現(xiàn)是合理的，但是當(dāng)N的值很大時(shí)，需要計(jì)算很長時(shí)間，是不切實(shí)際的。下面的結(jié)論可以得到一種更好的算法。 如果N是偶數(shù)，那么X^N =（X*X）^[N/2]； 如果N是奇數(shù)，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]； 其中[N]是指小于或等于N的最大整數(shù)。 C++實(shí)現(xiàn)功能函數(shù)： ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

/* 函數(shù)功能：利用模運(yùn)算規(guī)則，采用遞歸方式，計(jì)算X^N(% P) 函數(shù)名：PowerMod 輸入值：unsigned int x，底數(shù)x unsigned int n，指數(shù)n unsigned int p，模p 返回值：unsigned int，X^N(% P)的結(jié)果 */ unsigned PowerMod(unsigned x , unsigned n , unsigned p) { ??? if (!n) ???? ???return 0; ??? unsigned temp = PowerMod((x * x) % p , n >> 1 , p); //遞歸計(jì)算（X*X）^[N/2] ??? if (n & 1) //判斷n的奇偶性 ???? ???temp = (temp * x) % p; ??? return temp; }

轉(zhuǎn)載于:https://www.cnblogs.com/wangyouxuan/p/3270614.html

總結(jié)

以上是生活随笔為你收集整理的次方求模 http://acm.nyist.net/JudgeOnline/problem.php?pid=102的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。