long long Pow(long long a,long long b){ int ans = 1; for(int i=1; i<=b; i++) ans*=a; return ans;}或許有人說可以將
ans*=a改為ans=a*ans%1000;
但是我們來計算一下耗時：
#include <iostream>#include <cmath>#include <time.h> using namespace std;
long long Pow(long long a,long long b){ long long ans = 1; for(int i=1; i<=b; i++) ans=a*ans%1000; return ans;}int main() { clock_t start, finish; long long base, power; cin >> base >> power; start = clock(); cout << Pow(base, power) << endl; finish = clock(); cout << "the time cost is " << double(finish - start) / CLOCKS_PER_SEC; return 0;}雖然可以求出來，但時間非常長，因此引入了更好的算法：快速冪算法 ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c ( a * b ) % c = ( ( a % c ) * ( b % c ) ) % c ( a – b ) % c = ( ( a % c ) – ( b % c ) ) % c以上公式表達為代碼：
long long quickPow(long long a, long long b) { long long ans=1; while(b>0) { if(b%2==0) { b/=2; a = (a%1000)*(a%1000)%1000; }else{ b=b-1; ans=(a%1000)*(ans%1000)%1000; b/=2; a = (a%1000)*(a%1000)%1000; } } return ans;}long long quick(long long a,long long b){ long long ans=1; while(b>0) { if(b%2==1) { ans=(a%1000)*(ans%1000)%1000; } a = (a%1000)*(a%1000)%1000; b /= 2; } return ans;}long long quick(long long a,long long b){ long long ans=1; while(b>0) { if(b&1) { ans=(a%1000)*(ans%1000)%1000; } a = (a%1000)*(a%1000)%1000; b >>= 2; } return ans;}1、位邏輯運算符：
& （位 "與"） and
^ （位 "異或"）
| （位 "或"） or
~ （位 "取反"）
2 、移位運算符：
<< （左移）
>> （右移）
& 運算 ：2個都為1才是1
00111 & 00100= 11100
&運算通常用於二進位取位操作。
X &1的結果就是取X二進位的最末位。
最末位為0表示該數是偶數，
最末位為1表示該數為奇數
| 運算：1個為1即為1
00111 | 11111 =11100
X|1的結果就是把X二進位最末位強行變為1
如果需要把二進位最末位變成0，對這個數
X |1之後再減一就可以了，其實際意義就是把X這個數強行變成最近接的偶數
^ 運算 ：不同則為1，相同則為0
00111^ 11011=11100
^運算通常用於對二進位的特定一位進行取反操作，^運算的逆運算是它本身，也就是說兩次異或同一個數最後結果不變，即（a^b)^b=a；
~運算：把內存中的0和1全部取反
(~運算 有符號整型和無符號整型的區分）
<<運算
a<<b 表示把a轉為二進位後左移b位（在後面添加 b個0）。
例如100的二進位表示為1100100，100左移2位後（後面加2個零）：
1100100<<2 =110010000 =400。
#include<iostream>using namespace std;int main(){ int a=100; a=a>>2; cout<<a; return 0; }結果為400
可以看出，a<<b的值實際上就是a乘以2的b次方，因為在二進位數後面添加一個0就相當於該數乘以2，2個零即2的2次方 等於4。
通常認為a<<1比a*2更快，因為前者是更底層一些的操作。因此程序中乘以2的操作儘量用左移一位來代替。
>>運算
和<<相似，a>>b表示二進位右移b位（去掉末b位），相當於a除以2的b次方（取整）。
最大公約數的二進位算法用除以2操作來代替%（mod）運算，效率可以提高很多。
#include <iostream>using namespace std;long long quickPow(long long a,long long b){ long long ans = 1; while(b) { if(b&1) { ans=(a%1000)*(ans%1000)%1000; } a = (a%1000)*(a%1000)%1000; b >>= 2; } return ans;}long long pow(long long a,long long b){ long long ans = 1; for(int i=1; i<=b; i++) ans *= a; return ans;}int main() { cout<<quickPow(2, 20)<<endl; cout<<pow(2,20)<<endl; return 0;}