跟着姚桑学算法-a^b

基本算法题. 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;  
}