CH101 a^b(位运算)

描述

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

输入格式

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

输出格式

一个整数，表示a^b mod p的值。

样例输入

2 3 9

样例输出

8

题解：将b用2的次幂的和表示出来，对于每一个2的次幂，只有0个或者一个

得到式子

又

得到以下代码：

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn = 1e2+5;
int power(int a,int b,int p){
	int ans = 1%p;
	while(b){
		if(b&1)ans=(long long)ans*a%p;
		a=(long long)a*a%p;
		b >>= 1;
	}
	return ans;
}
int main(){
	int a,b,p;
	cin>>a>>b>>p;
	cout<<power(a,b,p);
	return 0;
}