求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; }
