高精度四则运算的C++代码实现

#include <stdio.h>
int Max(int a[],int n)
{
    int max=a[0],i;
    for(i=1;i<n;i++) if(a[i]>max) max=a[i];
    return max;
}
int T[100000];
void countSort(int a[], int n, int exp)
{
    int i,b[10]={0};
    for(i=0;i<n;i++) b[a[i]/exp%10]++;
    for(i=1;i<10;i++) b[i]+=b[i-1];
    for(i=n-1;i>=0;i--)
    {
        int t=a[i]/exp%10;
        T[b[t]-1]=a[i];
        b[t]--;
    }
    for(i=0;i<n;i++) a[i]=T[i];
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N];

//字符串类型转换为数组，并且倒过来
void stringToArr(string s, int a[])
{
    int len = s.length();
    //倒过来进行赋值
    for (int i = 0; i < len; i++)
    {
        a[i] = s[len - i - 1] - '0';
    }
}

//初始化字符串转换为数组
void init(string s1, string s2)
{
    //清0,全局变量只有第一次是0
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    //将其转为数字串，并倒过来
    stringToArr(s1, a);
    stringToArr(s2, b);
}

//数组转换为字符串，并且倒过来
string arrToString(int a[], int n)
{
    string s = "";
    //倒过来进行字符的还原
    for (int i = n - 1; i >= 0; i--)
    {
        s += (char)(a[i] + '0');
    }
    return s;
}

//两数比较，大于等于返回true
bool cmp(string a, string b)
{
    //位数不等，位数大的数大
    if (a.length() != b.length())
    {
        return a.length() > b.length();
    }
    //位数相等字典序大小即大小关系
    return a >= b;
}

//加法
string add(string s1, string s2)
{
    //先把s1和s2初始化到ab数组里
    init(s1, s2);
    //长度为两数最大的那个数
    int len = max(s1.length(), s2.length());
    //进位
    int step = 0;
    for (int i = 0; i < len; i++)
    {
        //当前位就是两数相加及进位的个位
        c[i] = (a[i] + b[i] + step) % 10;
        //当前位就是两数相加及进位的十位
        step = (a[i] + b[i] + step) / 10;
    }
    //进位不为0，所以要多一位
    if (step != 0)
        c[len++] = step;
    return arrToString(c, len);
}

//减法，只能大减小
string sub(string s1, string s2)
{
    //先把s1和s2初始化到ab数组里
    init(s1, s2);
    //s1是大数，所以他的长度就是ans的长度
    int len = s1.length();
    for (int i = 0; i < s1.length(); i++)
    {
        //小于就借位
        if (a[i] < b[i])
        {
            a[i] += 10;
            a[i + 1]--;
        }
        //进行减法
        c[i] = a[i] - b[i];
    }

    //去除前导0
    while (len > 1 && c[len - 1] == 0)
        len--; //把c数组转换为string类型输出，m作为位数传递
    return arrToString(c, len);
}

//乘法
string mul(string s1, string s2)
{
    //先把s1和s2初始化到ab数组里
    init(s1, s2);
    for (int j = 0, i; j < s2.length(); j++)
    {
        //进位为step
        int step = 0;
        for (i = 0; i < s1.length(); i++)
        {
            //就是列乘法计算，直接加进去目标位
            c[i + j] += a[i] * b[j] + step;
            //有可能产生进位，需要保存
            step = c[i + j] / 10;
            //目标位是一位数
            c[i + j] = c[i + j] % 10;
        }
        //最终进位还是空的，直接给进位吧
        c[i + j] = step;
    }
    //最终可能有两个总长的位数
    int len = s1.length() + s2.length();
    //去除前导0
    while (len > 1 && c[len - 1] == 0)
        len--;
    return arrToString(c, len);
}

//除法，返回余数，c是商
string div(string a, string b, string &c)
{
    //remainder的缩写，代表余数，也就是当前的被除数
    string rem = "";
    //c有可能会被操作了，清空一下
    c = "";
    for (int i = 0; i < a.length(); i++)
    {
        //余数为0，就是当前一位。否则加上当前位
        if (rem == "0")
            rem = a[i];
        else
            rem = rem + a[i];
        int t = 0;
        //如果被除数比除数大，进行减法，t最大也是9
        while (cmp(rem, b))
        {
            rem = sub(rem, b);
            t++;
        }
        //c还是空且t是0，直接进行下一次循环，解决了商的前导0
        if (c == "" && t == 0)
            continue;
        //商加上求出的当前位
        c = c + char(t + '0');
    }
    if (c == "")
        c = "0";
    return rem;
}
int main()
{
    string a, b, c;
    while (cin >> a >> b)
    {
        //加法
        cout << add(a, b) << "n";
        //减法，需先判断a b大小，小于交换，输出负号
        if (!cmp(a, b))
        {
            cout << "-";
            swap(a, b)
        }
        cout << sub(a, b) << "n";
        //乘法
        cout << mul(a, b) << "n";
        //除法使用，依次输出商和余数
        string d = div(a, b, c);
        cout << c << " " << d << "n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 2.1e6;
const double Pi = acos(-1);
int n, m, r[N], P, ans[N];
struct C
{
    double x, y;
} a[N], b[N];
C operator+(C a, C b) { return (C){a.x + b.x, a.y + b.y}; }
C operator-(C a, C b) { return (C){a.x - b.x, a.y - b.y}; }
C operator*(C a, C b) { return (C){a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y}; }

void FFT(C f[], int opt)
{
    for (int i = 0; i < n; ++i)
        if (i < r[i])
            swap(f[i], f[r[i]]);
    for (int len = 1, nl = 2; len < n; len = nl, nl <<= 1)
    {
        C rot = (C){cos(Pi / len), opt * sin(Pi / len)};
        for (int l = 0; l < n; l += nl)
        {
            C w = (C){1, 0};
            int r = l + len;
            for (int k = l; k < r; ++k, w = w * rot)
            {
                C x = f[k], y = w * f[k + len];
                f[k] = x + y, f[k + len] = x - y;
            }
        }
    }
}

string arrToString(int a[], int n)
{
    string s = "";
    while (n > 1 && a[n - 1] == 0)
        n--;
    for (int i = n - 1; i >= 0; i--)
    {
        s += (char)(a[i] + '0');
    }
    return s;
}

void stringToArr(string s, C a[])
{
    int len = s.length();
    for (int i = 0; i < len; i++)
    {
        a[i].x = s[len - i - 1] - '0';
    }
}

int main()
{
    string s, c;
    cin >> s;
    stringToArr(s, a);
    cin >> c;
    stringToArr(c, b);
    n = max(s.length(), c.length());
    for (m = n + n, n = 1; n <= m; n <<= 1, ++P)
        ;
    for (int i = 0; i < n; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (P - 1));
    //蝴蝶变换FFT
    FFT(a, 1), FFT(b, 1);
    for (int i = 0; i < n; ++i)
        a[i] = a[i] * b[i];
    FFT(a, -1);
    for (int i = 0; i <= m; ++i)
        ans[i] = (int)(a[i].x / n + .5);
    for (int i = 0, tmp1, tmp2; i < m; ++i)
        ans[i + 1] += (ans[i] / 10), ans[i] %= 10;
    cout << arrToString(ans, m + 1) << "n";
}

View Code