快速幂和快速幂求逆元

快速幂

利用倍增的思想，将o(n)的时间复杂度优化成o(lgn)

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

快速幂求逆元

求逆元就是为了把除法转化成乘法，因为乘法可以取模，而除法不行，除***有精度问题，而乘法则不会有这样的问题，要注意，有逆元的情况下是两个数必须要互质（也就是最大公约数为1）

通俗易懂的博客

int ksm(int a, int b,int mod) {
    int res = 1;
    while (b) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    cout << ksm(n, m - 2, m) <<endl;
}