基本算法题. a^b
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
0≤a,b≤10^9
1≤p≤109
输入样例：
3 2 7输出样例：
2:four_leaf_clover:题解 --- 数论
首先a^ b中可以设b=2^ t1+2^t2+…+2 ^ tk(二进制) 即将b转换为二进制表示，
b&1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false；
此外，b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数。
:memo:代码展示
// 迭代法
#include<iostream>
using namespace std;
int main()
{
long long a,b,p,res=1;
scanf("%ld%ld%ld",&a,&b,&p);
while(b)
{
if(b&1) res=res*a%p;
b>>=1;//b右移了一位后,a也需要更新
a=a*a%p;
}
printf("%ld\n",res%p);
}
// 递归法
#include<iostream>
using namespace std;
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
if(b==0) return 1%p;
a%=p;
ull res=quick_pow(a,b>>1,p);
if(b&1) return res*res%p*a%p;
return res*res%p;
}
int main()
{
int a,b,p;
cin.tie(0);
ios::sync_with_stdio(false);
cin>>a>>b>>p;
cout<<quick_pow(a,b,p)<<endl;
return 0;
}【知识点：进制转换】
在C++中，按照指定的进制格式输出：
#include <bitset>
#include<iostream>
using namespace std;
int main()
{
cout << "45的8进制:" << std::oct << 45<< endl;
cout << "45的10进制" << std::dec << 45 << endl;
cout << "45的16进制:" << std::hex << 45 << endl;
cout << "45的2进制: " << bitset<8>(45) << endl; //<8>：表示保留8位输出
return 0;
} 
