求a的b次方對c取余的值
3 2 3 5 3 100 10 11 12345 12345
3 1 10481
算法分析:
大數問題,需要利用快速冪取模算法。
所謂的快速冪,實際上是快速冪取模的縮寫,簡單的說,就是快速的求一個冪式的模(余)。在程序設計過程中,經常要去求一些大數對於某個數的余數,為了得到更快、計算范圍更大的算法,產生了快速冪取模算法。求a^b mod c = 幾。 (result就是取余後的結果)
算法1.普通算法:
int pow( int a, int b ) { int r = 1; while( b-- ) r *= a; return r; } result=r%c;這個算法的時間復雜度體現在while循環中,為O(b).這個算法存在著明顯的問題,如果a和b過大,很容易就會溢出。
算法2.二分法
int pow( int a, int b ) { int r = 1, base = a; while( b != 0 ) { if( b % 2 ) r *= base; base *= base; b /= 2; } return r; } result=r%c;算法三:快速冪取模算法
首先要了解這樣一個公式:a^b
mod c=(a mod c)^b mod c(詳細證明請看數論或者離散數學)
了解了這個公式,我們可以先讓a關於c取余,這樣可以大大減少a的大小, 於是不用思考的進行了改進,代碼如下:
int pow(int a, int b) { int r = 1; a = a % c; //加上這一句 while(b--) { r*=a; //為了使r每次的數值更小,保證數據大小的可行性,這裡可以改為 r=(r*a)%c; } } result = r % c;
這個算法在時間復雜度上沒有改進,仍為O(b),不過已經允許更大b值,但是在c過大的條件下,還是很有可能超時,所以,我們結合前面推出更快更好快速冪算法。 快速冪算法依賴於以下明顯的公式,我就不證明了。
我們可以看到,我們把時間復雜度變成了O(b/2).當然,這樣子治標不治本。但我們可以看到,當我們令k = (a * a) mod c時,狀態已經發生了變化,我們所要求的最終結果即為(k)b/2 mod c而不是原來的ab mod c,所以我們發現這個過程是可以迭代下去的。當然,對於奇數的情形會多出一項a
mod c,所以為了完成迭代,當b是奇數時,我們通過 ans = (ans * a) % c;來彌補多出來的這一項,此時剩余的部分就可以進行迭代了。
形如上式的迭代下去後,當b=0時,所有的因子都已經相乘,算法結束。於是便可以在O(log b)的時間內完成了。於是,有了最終的算法:快速冪算法。 代碼如下:
int Pow(int a, int b, int c) { int r = 1; a = a % c; while(b>0) { if(b % 2 = = 1) r = (r * a) % c; b = b/2; a = (a * a) % c; } return r; }
利用位操作實現快速冪的代碼如下:(測試了下這種求冪法能力很有限,如果不在中間取模,,很容易就溢出了)
#include#include _int64 pow( _int64 a, _int64 b ); int main() { _int64 a,b,c; int n; scanf("%d",&n); printf("%d\n",100&1); while(n--){ scanf("%I64d%I64d%I64d",&a,&b,&c); printf("%I64d\n",pow(a,b)%c); } return 0; } _int64 pow( _int64 a, _int64 b ) { _int64 r = 1, base = a; printf("%I64d %I64d\n",a,b); while( b != 0 ) { if( b & 1 ) r *= base; base *= base; printf(" %I64d %I64d\n",r,b); b >>= 1; } return r; }
本題代碼如下:
#include#include long long pow(long long a,long long b,long long c); int main(void) { long long a,b,c; int n; scanf("%d",&n); while(n--){ scanf("%lld%lld%lld",&a,&b,&c); printf("%lld\n",pow(a,b,c)); } return 0; } long long pow(long long a,long long b,long long c) { int r=1; a=a%c; while(b>0){ if(b%2==1) r=(r*a)%c; b=b/2; a=(a*a)%c; } return r; }