快速幂(模版）

 //求x^y%mod

ll quick(ll x,ll y,ll mod){   
    ll ans=1;
    while(y){
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y/=2;
    }
    return ans;
}

//求a^n%mod  (mod 在前面定义了)
ll quick(ll a,ll n) 
{
    ll re=1;
    while(n)
    {
        if(n&1) //判断n的二进制最后一位是不是1，或者说判断n是不是奇数
        {
            re=(re*a)%mod;
        }
        n>>=1;  //除掉n二进制的最后一位，相当于/2
        a=(a*a)%mod;
    }
    return re%mod;
}

//快速幂取余全都用long long不固定代码：
long long quick(long long x,long long y,long long n)
{
    long long ans=1;
    while(y)
    {
        if(y%2==1)
        ans=ans*x%n;
        x=x*x%n;
        y/=2;
    }
    return ans;
}

不知道为啥，现在才整理快速幂的相关知识，很多东西还是整理下来吧，方便以后的学习跟总结。

简单的相关知识：
1.&（按位与运算符）
x&1==1，则表示x为奇数；
x&1==0，则表示x为偶数；

2.>> <<（移位运算符）
"<<" :左移
">>" :右移

数学意义：右移移位相当于除以2，右移n位相当于除以2^n。左移同理
例如：11>>2=2(11换成二进制：1011，右移两位为10，换成十进制为2）

先举一个最简单的例子：2^13 = 2^(1101) = 2^8 * 2^4 * 2^1
快速幂代码：求a^n
ll qpow(ll a,ll n)
{
    ll re=1;
    while(n)
    {
        if(n&1) //判断n的二进制最后一位是不是1，或者说判断n是不是奇数
        {
            re=(re*a)%mod;
        }
        n>>=1;  //除掉n二进制的最后一位
        a=(a*a)%mod;
    }
    return re%mod;
}