Neovim-如何使用编辑器的神

快速幂算法

https://www.acwing.com/problem/content/877/

快速幂主要用来在$O(logk)$的时间复杂度内, 求出$a^{k} \%p$的值, 其中$a, k, p$都可以在$10^9$范围.

核心就是利用二进制, 将$a^{k}$拆分成若干个预处理数的乘积, 例如可以这样拆:

$a^{k} = a^{2^{c_0} + 2^{c_1} + 2^{c_2} + …+2^{c_m}} = a^{2^{c_0}} \times a^{2^{c_1}} \times a^{2^{c_2}} \times … \times a^{2^{c_m}}$

其中, $a^{2^{c_0}}, a^{2^{c_1}}, …, a^{2^{c_m}}$都可以通过预处理进行.

我可以遍历$k$的二进制位, 如果第$i$位是1, 就需要乘上$a^{2^{c_i}}$.

#include <iostream>

using namespace std;

typedef long long LL;

int n;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
      // 可能超int, 先变成LL再取模
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    cin >> n;

    while (n --)
    {
        int a, k, p;
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }
    return 0;
}

64位整数乘法

https://www.acwing.com/problem/content/description/92/

#include <iostream>

using namespace std;

typedef long long LL;

LL a, b, p;

LL qmi(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;

    return 0;
}

两数相除

https://leetcode.cn/problems/divide-two-integers/

首先考虑被除数$a$和除数$b$都是正数的例子.

首先预处理出来$2^{0}b,\ 2^{1}b,\ 2^{2}b, …, 2^{k}b$, 其中$2^{k+1}b > a$.

$i$从$k$到0遍历, 假设$a - 2^{i}b > 0$, 那么商的二进制表示中, 第$i$位肯定是1, 然后将$a$减去$2^{i}b$, 重复上面的过程, 即可在$O(log_ba)$的时间复杂度内求出商.

class Solution {
public:
    int divide(int x, int y) {
        typedef long long LL;

        bool is_minus = false;
        if ((x < 0 && y > 0) || (x > 0 && y < 0)) is_minus = true;

        LL a = abs((LL)x), b = abs((LL)y);

        vector<LL> exp;
      // 预处理2^0b, 2^1b, ...
        for (LL i = b; i <= a; i = i + i) exp.push_back(i);

        LL res = 0;

        for (int i = exp.size() - 1; i >= 0; i --) {
            if (a >= exp[i]) {
                a -= exp[i];
                // 注意这里一定是1ll
                res += 1ll << i;
            }
        }

        if (is_minus) res = -res;

        if (res < INT_MIN) return INT_MIN;
        if (res > INT_MAX) return INT_MAX;
        return res;
    }
};

Pow(x, n)

https://leetcode.cn/problems/powx-n/

快速幂, 注意int溢出

class Solution {
public:
    double myPow(double x, int n) {

        typedef long long LL;

        bool is_minus = false;
        if (n < 0) is_minus = true;

        double res = 1.0;
        // 一定是longlong, n有可能是-2147483648, abs之后就超出int范围
        LL k = (LL)abs((LL)n);

        while (k) {
            if (k & 1) res = res * x;
            x = x * x;
            k >>= 1;
        }

        if (is_minus) res = 1.0 / res;
        return res;
    }
};

数值的整数次方

https://www.acwing.com/problem/content/description/26/

class Solution {
public:
    double Power(double base, int exponent) {

        typedef long long LL;

        if (exponent == 0) return 1.0;

        double res = 1.0;

        double a = base;
        LL k = (LL)abs((LL)exponent);

        while (k)
        {
            if (k & 1) res = res * a;
            a = a * a;
            k >>= 1;
        }
        if (exponent < 0) res = 1.0 / res;
        return res;
    }
};