【题目链接】
http://poj.org/problem?id=1995
【算法】
- 基本快速幂(二进制思想)
- 注意两个int相乘可能溢出,加(long long)但是相乘不要加括号,不然会先溢出在类型转换
1 #include <iostream> 2 using namespace std; 3 int z,m,h,cur,ans,a,b; 4 void calc() 5 { 6 cin>>a>>b; 7 cur = 1 % m; 8 for(; b; b >>= 1) { 9 if(b & 1) cur = (long long)cur * a % m; 10 a = (long long)a * a % m; 11 } 12 ans = (long long)(ans+cur) % m; 13 } 14 int main() 15 { 16 cin>>z; 17 while(z--) 18 { 19 ans = 0; 20 cin>>m>>h; 21 while(h--) calc(); 22 cout << ans%m << endl; 23 } 24 }