前置函数

数学取模

1
2
3
4
int Mod(int x,int mod)
{
    return (x % mod + mod) % mod;
}

比较大小

1
2
3
4
5
6
7
8
9
10
11
int cmp(string a, string b)
{
    if (a.length() > b.length()) return 1;
    else if (a.length() < b.length()) return -1;
    else
    {
        if (a < b) return -1;
        else if (a > b) return 1;
        else return 0;
    }
}

int转string

1
2
3
4
5
6
void i2s(int& x,string& s)
{
    stringstream ss;
    ss << x;
    ss >> s;
}

高精度

思路

用代码模拟小学所学的竖式加/减
将乘除转化为加/减

加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
string Myadd(string a, string b)
{
    //a = a.substr(a.find_first_not_of('0'));
    //b = b.substr(b.find_first_not_of('0'));
    long long len = 0;
    if (a.length() > b.length())
    {
        len = a.length() + 10;
    }
    else
    {
        len = b.length() + 10;
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string ans(len, '0');
    for (int i = 0; i < a.length(); i++)
    {
        ans[i] = a[i];
    }
    int tmp = 0;
    for (int i = 0; i < len; i++)
    {
        if (i < b.length())
        {
            tmp += (ans[i] - '0') + (b[i] - '0');
            ans[i] = tmp % 10 + '0';
            tmp /= 10;
        }
        else
        {
            tmp += (ans[i] - '0');
            ans[i] = tmp % 10 + '0';
            tmp /= 10;
        }
    }
    reverse(ans.begin(), ans.end());
    if (ans.find_first_not_of('0') != string::npos)
    {
        ans = ans.substr(ans.find_first_not_of('0'));
        return ans;
    }
    else
    {
        return "0";
    }
}

减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
string Mysub(string a, string b)
{
    int flag = 0;
    if(cmp(a, b)<0)
    {
        string tmp = a;
        a = b;
        b = tmp;
        flag = 1;
    }
    //a = a.substr(a.find_first_not_of('0'));
    //b = b.substr(b.find_first_not_of('0'));
    long long len = 0;
    if (a.length() > b.length())
    {
        len = a.length() + 10;
    }
    else
    {
        len = b.length() + 10;
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string ans(len, '0');
    for (int i = 0; i < a.length(); i++)
    {
        ans[i] = a[i];
    }
    int tmp = 0;
    for (int i = 0; i < len; i++)
    {
        if (i < b.length())
        {
            tmp += (ans[i] - '0') - (b[i] - '0');
            ans[i] = Mod(tmp,10) + '0';
            tmp = (tmp - 9) / 10;
        }
        else
        {
            tmp += (ans[i] - '0');
            ans[i] = Mod(tmp, 10) + '0';
            tmp = (tmp - 9) / 10;
        }
    }
    reverse(ans.begin(), ans.end());
    if (ans.find_first_not_of('0') != string::npos)
    {
        if (flag == 1)
        {
            ans[ans.find_first_not_of('0') - 1] = '-';
        }
        ans = ans.substr(ans.find_first_not_of('0'));
        return ans;
    }
    else
    {
        return "0";
    }
}

乘法

1
2
3
4
5
6
7
8
9
10
11
string Mymul(string a, string b)
{
    string cnt;
    string ans;
    while (cnt != b)
    {
        ans = Myadd(ans, a);
        cnt = Myadd(cnt, "1");
    }
    return ans;
}

除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
string Mydiv(string a, string b)
{
    int cnt = 0;
    while (cmp(a, b) > 0)
    {
        a = Mysub(a, b);
        cnt++;
    }
    string ans;
    i2s(cnt, ans);
    ans.append(".");
    for (int i = 0; i <= 101; i++)
    {
        int t = 0;
        a.append("0");
        while (cmp(a, b) < 0)
        {
            a.append("0");
            ans.append("0");
        }
        while (cmp(a, b) >= 0)
        {
             a = Mysub(a, b);
             t++;
        }
        string t_str;
        i2s(t, t_str);
        ans.append(t_str);
    }
    return ans;
}

取模

1
2
3
4
5
6
7
8
string Mymod(string a, string b)
{
    while (cmp(a, b) > 0)
    {
        a = Mysub(a, b);
    }
    return a;
}