说明

此文章为作者整理的一些常见的基础算法模板。常用于各种题目的时间复杂的优化上。

1.快速幂

【模板】快速幂普及-

原题链接：https://www.luogu.com.cn/problem/P1226

题目描述：

给你三个整数 $a, b, p$ ，求 $a*^{b} mod p$ 。
输入格式：输入只有一行三个整数，分别代表 a,b,p。
输出格式：输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。

示例

输入：2 10 9
输出：2^10 mod 9=7
说明：210=1024，1024 mod 9 = 7。

代码

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

void solve()
{
    int a , b , p;
    cin >> a >> b >> p;
    cout << a << "^" << b << " mod " << p << "=" << qmi(a , b , p) << endl; 
}

2.高精度运算

A + B Problem (高精) 普及-

原题链接：https://www.luogu.com.cn/problem/P1601

题目描述

高精度加法，相当于 a+b problem，不用考虑负数。
输入格式：分两行输入。a,b≤10^500。
输出格式：输出只有一行，代表 $a + b$ 的值。

示例

输入： 1 1
输出：2

代码

inline vector<int> add(vector<int> &a , vector<int> &b)
{
    if (a.size() < b.size()) return add(b , a);
    
    vector<int> res;	
    int t = 0;
    for (int i = 0 ; i < a.size() ; i ++ )
    {
        t += a[i];
        if (i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;	
    }	
    
    if (t) res.push_back(t);
    
    reverse(ALL(res));
    return res;
}

void solve()
{
    string s1 , s2;
    cin >> s1 >> s2;
    vector<int> a , b;
    for (auto i : s1) a.push_back(i - '0');
    for (auto i : s2) b.push_back(i - '0');
    
    reverse(ALL(a)) , reverse(ALL(b));
    auto ans = add(a , b);
        
    for (auto i : ans) cout << i;
    cout << endl; 
}

高精度减法普及-

原题链接：https://www.luogu.com.cn/problem/P2142

题目描述

高精度减法。
输入格式：两个整数 $a, b$ （第二个可能比第一个大）。
输出格式：结果（是负数要输出负号）。

示例

输入：2 1
输出：1

代码

bool cmp(vector<int> a , vector<int> b)
{
    if (a.size() != b.size()) return a.size() > b.size();
    
    for (int i = 0 ; i < a.size() ; i ++ )
    {
        if (a[i] != b[i]) return a[i] > b[i];
    }
    
    return true;
}

inline vector<int> sub(vector<int> &a , vector<int> &b)
{
    vector<int> res;
    int value = 0;
    for (int i = 0 ; i < a.size() ; i ++ )
    {
        value = a[i] - value;
        
        if (i < b.size()) value -= b[i];
        
        res.push_back((value + 10) % 10);
        
        if (value < 0) value = 1;
        else value = 0;
    }
    
    while (res.size() > 1 && !res.back()) res.pop_back();
    
    reverse(ALL(res));
    return res;
    
}

void solve()
{
    string s1 , s2;
    cin >> s1 >> s2;
    vector<int> a , b;
    for (auto i : s1) a.push_back(i - '0');
    for (auto i : s2) b.push_back(i - '0');
    
    reverse(ALL(a)) , reverse(ALL(b));

    if (cmp(a , b))
    {
        auto ans = sub(a , b);
        for (auto i : ans) cout << i;
        cout << endl;
    }
    else 
    {
        cout << '-';
        auto ans = sub(b , a);
        for (auto i : ans) cout << i;
        cout << endl;
    }
}

高精度乘法

原题链接：https://www.lanqiao.cn/problems/1943/learning/?page=1&first_category_id=1&name=%E9%AB%98%E7%B2%BE%E5%BA%A6

题目描述

给定两个位数不超过100位的正整数，求它们的乘积。
输入格式：输入文件中包含多个测试数据。每个测试数据占两行，分别为一个正整数，每个正整数的位数不超过100位。输入数据一直到文件尾。
输出格式：对每个测试数据，输出其中两个正整数的乘积。

示例

输入：
981567
32976201
123456789
987654321
输出：
32368350686967
121932631112635269

代码

vector<int> mul(vector<int> &a , vector<int> &b)
{
    vector<int> res(a.size() * b.size());
    
    for (int i = 0 ; i < b.size() ; i ++ )
        for (int j = 0 ; j < a.size() ; j ++ )
            res[i + j] += b[i] * a[j];

    for (int i = 0 ; i < a.size() + b.size() - 1 ; i ++ )
    {
        if (res[i] > 9)
        {
            res[i + 1] += res[i] / 10;
            res[i] %= 10;
        }
    }

    while (res.size() > 1 && !res.back()) res.pop_back();
    reverse(ALL(res));
    return res;
}


void solve()
{
    string s1 , s2;
    while (cin >> s1 >> s2)
    {
        vector<int> a , b;
        for (auto i : s1) a.push_back(i - '0');
        for (auto i : s2) b.push_back(i - '0');
        
        reverse(ALL(a)) , reverse(ALL(b));
        auto ans = mul(a , b);

        for (auto i : ans) cout << i;
        cout << endl;
    }
}