数论1 : 取模以及快速幂

数论1 : 取模以及快速幂

取模:

取模拥有一些非常棒的性质：
\[ (a+b)\mod p =((a \mod p)+(b \mod p)) \mod p \]

\[ (a-b)\mod p=((a\mod p)-(b \mod p))\mod p \]

\[ (a\times b)\mod p=((a\mod p)\times(b\mod p))\mod p \]

\(\text{ }\)注意：除法时需要用到乘法逆元。

取模通常用于最后答案较大的题目里，多用于数论题或动态规划题。

快速幂

通常用来求类似于\(a^n \mod p\)的结果，由于取模有结合律，所以我们可以将复杂度从\(O(n)\)优化到\(O(log_2n)\):

对于\(a^n \mod p:\)
\[ \text{如果n是偶数,则}a^n\mod p=(a^{\frac{n}{2}}\mod p )\times(a^{\frac{n}{2}}\mod p)\mod p \]

\[ \text{如果n是奇数,则}a^n\mod p=(a^{\frac{n}{2}}\mod p)\times (a^{\frac{n}{2}}\mod p) \times a \mod p \]

实现代码，相当于模拟二进制：

ll ksm(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1) res=(res*x)%mo;
        x=(x*x)%mo;
        p>>=1;
    }
    return res%mo;
}

龟速乘

通常应对模数较大，两数相乘直接爆longlong的情况,类似于\(a \times b \mod p\).

其实乘除或者开方等运算本质上就是加减。

实现代码:

ll gsc(ll x,ll p){
    ll res=0;
    while(p){
        if(p&1) res=(res+x)%mo;
        x=(x+x)%mo;
        p>>=1;
    }
    return res%mo;
}

数论1 : 取模以及快速幂

原文：https://www.cnblogs.com/Rachel-in/p/11197060.html