按位与（Bitwise AND）是一种二进制运算，它逐位对两个数的二进制表示进行运算。对于每一位，只有两个相应的位都为1时，结果位才为1；否则，结果位为0。如：十进制9 & 5转化为二进制：(1001)&(0101)=0001。

>> <<

• 左移（<<）：将一个无符号整数左移n位，相当于将该数乘以2n。这是因为每向左移动一位，就相当于在数的末尾添加了一个0（在二进制表示中），这等价于乘以2。

• 右移（>>）：将一个无符号整数右移n位，相当于将该数除以2n并向下取整。这是因为每向右移动一位，就相当于去掉了数末尾的一个0（或更准确地说，是将数除以2并丢弃余数），这等价于除以2.
  无符号代表没有溢出，如果有符号为int，则可能会爆int

快速幂：快速的求出一个幂mod一个数的值
假设

 

题目：875. 快速幂 - AcWing题库 

代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

int n;

int quick_mi(int a,int b,int p)
{
    LL res=1%p;
    while(b)
    {
        //将b转化为2进制时按位与1，当b=0时，结束快速幂
        if(b&1) res=res*a%p;
        //舍弃b在二进制下的最后一位
        b = b >> 1;
        //上一个a^2%p
        a=(LL)a*a%p;
    }
    
    return res;
}

int main()
{
    scanf("%d",&n);
    
    while(n--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        
        printf("%d\n",quick_mi(a,b,c));
    }
    
    return 0;
}

题目：876. 快速幂求逆元 - AcWing题库

 题目即是要求：b^(m-2)。

证明：
由若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a*x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b^(-1)(mod m)。等式两端约去a，得1/b≡b^(-1)(mod m)➡等式两端同时乘以b，得1≡b^(-1)*b(mod m)。也就是b*b^(-1)≡1(mod m),因为b与m互质，且m为质数，由费马小定理可得b^(m-1)≡1(mod m),也就是b*b^(m-1)≡1(mod m),所以b^(m−2) 即为 b的乘法逆元

代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int n;

int quick_mi(int a,int b,int p)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    
    return res;
}

int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int t=quick_mi(a,b-2,b);
//特判一下，只有当a与b互质时才成立
        if(a%b) printf("%d\n",t);
        else printf("impossible\n");
    }
    
    return 0;
    
}