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 log n)$的时间复杂度内计算出它们的乘积，并最终得到乘积的各位数字。
复杂度：$o(nlog(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;//存储位逆序排列后的结果，初始化为0
for(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位反转后的值赋给j
if (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]赋值为0
else 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]赋值为0
else 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;
}