数论之模运算+快速幂

模运算

/定义

　　取模运算为a除以m的余数，记为：a mod m = a % m

取模的结果满足0 ≤ a mod m ≤ m-1，题目用给定的m限制计算结果的范围。例如m=10，输出结果为原数的个位

/性质

　　加：( a + b ) mod m = (( a mod m ) + ( b mod m )) mod m

　　减：( a  - b ) mod m = (( a mod m )  - ( b mod m )) mod m

　　乘：( a × b ) mod m = (( a mod m ) × ( b mod m )) mod m

　　注意：没有除法！！

　　　　　( a / b ) mod m =(( a mod m ) / ( b mod m )) mod m  

　　打个比方 ( 100 / 50 ) mod 20 = 2，(( 100 mod 20 ) / ( 50 mod 20 )) mod 20 = 0 ，但 2 ≠ 0

快速幂

直接上代码。。

ll fastpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(a*ans)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

假设要计算, 当n很大时，例如n=1e9，如果直接计算，就会发现计算结果的数字太大，计算结果的时间复杂度也是O(n)。

为了降低时间复杂度，我们采用快速幂的方法，用二进制表示n，然后将表示为多个2的指数幂的和

由于幂运算的结果非常大，常常会超过变量类型的最大值。因此，建议在运算过程中就对每一个a进行取模，然后将它们相乘，最后再计算取模值。

数论之模运算+快速幂

原文：https://www.cnblogs.com/ynzhang2020/p/15120449.html