首页 > 其他分享 >快速幂模板 + 快乘模板 + 取模方式

快速幂模板 + 快乘模板 + 取模方式

时间:2022-10-31 10:44:10浏览次数:101  
标签:取模 int LL ans 快速 复杂度 模板

​​​​​​​​​​​​​​​​​​​​
​​

取模,变小
(这里减法取模和除法取模需要特别注意)
1.加法取模: (A + B)% P = (A % P + B % P) % P
2.乘法取模: (A * B) % P = (A % P * B % P) % P
3.减法取模: (A - B)% P = (A % P - B % P + P ) % P (要加上P);
4.整除取模: (A / B)% P = (A % P * B ^ (P - 2) % P) %P)

快乘模板 : a * b % mod 当 a 和 b 很大,超出了longlong 的范围的时候,解决的方式是,使用快乘模板

//求得 a ^ b % c 的值
int multiMod(int a, int b, int c)
{
    int ans = 0;//注意初始化是0,不是1
    
    while (b)
    {
        if (b & 1)
            ans=(ans+a)%c;
        a = (a + a) % c;//和快速幂一样,只不过这里是加
        b >>= 1;
    }
    return ans; 
}

快速幂模板(使用的较多, 时间复杂度是O(logn),朴素的写法复杂度是 O(n))

模板:

//a ^ b % c
LL poww(LL a, LL b, LL c)
{
    LL ans = 1; //其一与快乘不一样的地方
    a = a % c;
    while(b>0)
    {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;  //其二与快乘不一样的地方
    }
    return ans;
}

标签:取模,int,LL,ans,快速,复杂度,模板
From: https://www.cnblogs.com/luoyefenglin/p/16843528.html

相关文章