高精度乘法C++

1.高精度乘高精度的简单算法

思想：倒置相乘，统一处理进位，还原。

复杂度： $o(n^2)$

// By SnowDream
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
string s1,s2;
int n1[N],n2[N],n3[N];//n1储存被乘数，n2储存乘数，n3储存积void mul()
{int l1=(int)s1.size();int l2=(int)s2.size();//读取字符串转换为int类型并倒置储存至数组for(int i=0;i<l1;++i){n1[l1-1-i]=s1[i]-'0';}for(int i=0;i<l2;++i){n2[l2-1-i]=s2[i]-'0';}for(int i=0;i<l1;++i){for(int j=0;j<l2;++j){n3[i+j]+=n1[i]*n2[j];}}//处理进位int l_max=l1+l2;for(int i=0;i<l_max;++i){n3[i+1]+=n3[i]/10;n3[i]%=10;}if(n3[l_max])l_max++;while(n3[l_max-1]>=10){n3[l_max]=n3[l_max-1]/10;n3[l_max-1]%=10;l_max++;}while(n3[l_max-1]==0&&l_max>1)l_max--;for(int i=l_max-1;i>=0;i--){cout << n3[i];}
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> s1 >> s2;mul();return 0;
}

2.高精度乘高精度FFT优化算法

思想：将两个大整数看作多项式的系数，然后利用FFT算法在 $O (n l o g n)$ 的时间复杂度内计算出它们的乘积，并最终得到乘积的各位数字。

复杂度： $o (n l o g (n))$

具体步骤：

将输入的两个大整数转换为对应的多项式表示，其中每个数字位作为多项式的系数。
对两个多项式进行补零操作，使其长度变为2的幂，方便进行FFT运算。
利用FFT算法对两个多项式进行快速傅里叶变换，得到它们在频域上的表示。
将两个多项式在频域上进行点乘操作，得到它们的乘积在频域上的表示。
对乘积进行逆FFT操作，得到乘积多项式在时域上的表示。
对乘积多项式进行进位处理，并输出最终的乘积结果。

// By SnowDream
#include<bits/stdc++.h>
using namespace std;#define L(x) (1<< (x))
typedef long long ll;
const int N=1e5+10;const double PI = acos(-1.0);
string s1,s2;
double ax[N],ay[N],bx[N],by[N];
int n1[N],n2[N],n3[N];//将一个整数x的二进制表示进行位逆序排列，并返回结果。
// 函数接受两个参数：整数x和表示位数的整数bits
int reverseBits(int x, int bits)
{int ret = 0;//存储位逆序排列后的结果，初始化为0for(int i=0;i<bits;++i)//循环bits次，对x的二进制表示进行位逆序排列{ret <<= 1;//将ret左移一位，为下一位的值腾出位置ret |=x&1;//将x的最低位与ret进行或操作，将x的最低位值添加到ret的最低位x >>=1;//将x右移一位，准备处理下一位}return ret;
}void fft(double * a, double * b, int n, bool rev)
{int bits = 0;// 计算n的二进制表示中位数while (1 << bits < n) ++bits;// 找到大于n的最小的2的幂for (int i = 0; i < n; i++){int j = reverseBits(i, bits);// 将i按照bits位反转后的值赋给jif (i < j)// 交换a和b数组中i和j位置的值{swap(a[i], a[j]);swap(b[i], b[j]);}}for (int len = 2; len <= n; len <<= 1)// 迭代每个长度为len的子序列{int half = len >> 1;// 子序列长度的一半double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);// 计算旋转因子的实部和虚部if (rev) wmy = -wmy;// 如果是逆变换，则虚部取相反数for (int i = 0; i < n; i += len)// 遍历每个子序列的起始位置{double wx = 1, wy = 0;// 初始化旋转因子for (int j = 0; j < half; j++)// 遍历子序列的前半部分{double cx = a[i + j], cy = b[i + j];// 获取当前位置的实部和虚部double dx = a[i + j + half], dy = b[i + j + half];// 获取对应的另一半的实部和虚部double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;// 计算旋转后的值a[i + j] = cx + ex, b[i + j] = cy + ey;// 更新前半部分的值a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;// 更新后半部分的值double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;// 计算下一个旋转因子wx = wnx, wy = wny;// 更新旋转因子}}}if (rev){for (int i = 0; i < n; i++)a[i] /= n, b[i] /= n;// 对结果进行归一化}
}int solve(int l1,int l2,int ans[])
{int len = max(l1, l2), ln;for(ln=0; L(ln)<len; ++ln);// 找到大于len的最小的2的幂len=L(++ln);// 计算2的幂for (int i = 0; i < len ; ++i){if (i >= l1) ax[i] = 0, ay[i] =0;// 如果i超过l1，则ax[i]和ay[i]赋值为0else ax[i] = n1[i], ay[i] = 0;// 否则将n1[i]赋值给ax[i]，ay[i]赋值为0}fft(ax, ay, len, false);// 进行快速傅里叶变换for (int i = 0; i < len; ++i){if (i >= l2) bx[i] = 0, by[i] = 0;// 如果i超过l2，则bx[i]和by[i]赋值为0else bx[i] = n2[i], by[i] = 0;// 否则将n2[i]赋值给bx[i]，by[i]赋值为0}fft(bx, by, len, false);// 进行快速傅里叶变换for (int i = 0; i < len; ++i){double cx = ax[i] * bx[i] - ay[i] * by[i];// 计算乘积的实部double cy = ax[i] * by[i] + ay[i] * bx[i];// 计算乘积的虚部ax[i] = cx, ay[i] = cy;// 更新ax和ay数组的值}fft(ax, ay, len, true);// 进行逆快速傅里叶变换for (int i = 0; i < len; ++i)ans[i] = (int)(ax[i] + 0.5);// 四舍五入取整return len;
}void mul()
{int l;int i;string ans;memset(n3, 0, sizeof(n3));int l1 = (int)s1.size();int l2 = (int)s2.size();for(i = 0; i < l1; i++)n1[i] = s1[l1 - i - 1]-'0';for(i = 0; i < l2; i++)n2[i] = s2[l2-i-1]-'0';l = solve(l1,l2, n3);for(i = 0; i<l || n3[i] >= 10; i++) // 进位{n3[i + 1] += n3[i] / 10;n3[i] %= 10;}l = i;while(n3[l] <= 0 && l>0) l--; // 检索最高位for(i = l; i >= 0; i--)cout << n3[i]; // 倒序输出
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> s1 >> s2;mul();cout << "\n";return 0;
}

3.高精度乘单精度

思想：倒置相乘，统一处理进位，再还原。

复杂度： $o (n)$

// By SnowDream
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
string s1;
int s2;
int n1[N];
void mul()
{string ans;int l1 = (int)s1.size();for(int i=0;i<l1;++i){n1[l1-1-i]=s1[i]-'0';}int w=0;for(int i=0;i<l1;++i){n1[i]=n1[i]*s2+w;w=n1[i]/10;n1[i]=n1[i]%10;}while(w){n1[l1++]=w%10;w/=10;}for(int i=l1-1;i>=0;i--)cout << n1[i];
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cin >> s1 >> s2;mul();cout << "\n";return 0;
}