机试第6章

大整数加法

string add(string a, string b)
{
    if (a.size() > b.size())
        a = string(a.size() - b.size(), '0') + a;
    else
        b = string(b.size() - a.size(), '0') + b;
    int carry = 0;
    string res(a.size(), ' ');
    for (int i = res.size() - 1; i >= 0; --i)
    {
        int cur = a[i] - '0' + b[i] - '0' + carry;
        res[i] = cur % 10 + '0';
        carry = cur / 10;
    }
    if (carry)
        return '1' + res;
    else
        return res;
}

大整数乘法

string mul(string str, int x)
{
    string res(str.size(), ' ');
    int carry = 0;
    for (int i = res.size() - 1; i >= 0; --i)
    {
        int cur = (str[i] - '0') * x + carry;
        str[i] = cur / 10 + '0';
        carry = cur % 10;
    }
    if (carry)
        return to_string(carry) + res;
    else
        return res;
}

string mul(string a, string b)
{
    string res = "0";
    for (int i = 0; i < b.size(); ++i)
    {
        int x = b[b.size() - 1 - i] - '0';
        string cur = mul(a, x);
        for (int j = 0; j < i; ++i)
            cur = mul(cur, 10);
        res = add(res, cur);
    }
    return res;
}

大整数除法

string divide(string str, int x)
{
    int remainder = 0;
    for (int i = 0; i < str.size(); ++i)
    {
        int cur = remainder * 10 + str[i] - '0';
        str[i] = cur / x + '0';
        remainder = cur % x;
    }
    int pos = 0;
    while (str[pos] == '0')
        pos++;
    return str.substr(pos);
}

最大公约数

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

最小公倍数

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

线性筛

const int MAXN = 1e4 + 5;
vector<int> pri;
int vis[MAXN];

void init(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i])
            pri.push_back(i);
        for (int j = 0; j < pri.size(); ++j)
        {
            if (1ll * i * pri[j] > n)
                break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
}

分解质因数

vector<int> factor;

for (int i = 0; i < pri.size() && pri[i] < n; ++i)
    while (n % pri[i] == 0)
        factor.push_back(pri[i]);
if (n > 1)
    factor.push_back(n);

快速幂

const int MOD = 114514;

int fpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
} 

矩阵快速幂

matrix fpow(matrix x, int k)
{
    mat res(x.row, x.col);
    for (int i = 0; i < res.row; ++i)
        for (int j = 0; j < res.col; ++j)
            if (i == j)
                res.mat[i][j] = 1;
            else
                res.mat[i][j] = 0;
    while (k)
    {
        if (k & 1)
            res = mul(res, k);
        k >>= 1;
        x = mul(x, x);
    }
    return res;
}

判断大整数是否可被整除

bool isDividable(string str, int k)
{
    int total = 0;
    for (int i = 0; i < str.size(); ++i)
    {
        total *= 10;
        total += str[i] - '0';
        total %= k;
    }
    return total == 0;
}