问题 : 【快速幂】a^b

时间限制: 1 Sec 内存限制: 128 MB

提交: 703 解决: 159

[提交] [状态] [讨论版] [命题人:admin]

题目描述

求 a 的 b 次方对 p 取模的值，其中 1≤a,b,p≤109

输入

三个用空格隔开的整数a,b和p。

输出

一个整数，表示ab mod p的值。

样例输入

2 3 9

样例输出

8

#include 
     
      #include 
      
       #define ll long long using namespace std ; ll quick_pow( ll a , ll b , ll p ){    ll ans = 1 % p , base = a ;    while ( b ){        if ( b & 1 ){            ans = (ans % p * base % p) % p ;        }        base = base * base % p ;        b >>= 1 ;    }    return ans ;} int main(){    ll a , b , p ;    while ( scanf("%lld %lld %lld" , &a , &b , &p) != EOF ){        printf("%lld\n" , quick_pow(a , b , p)) ;    }    return 0 ;}