如下,这个代码:
#include <bits/stdc++.h>
using namespace std;
const long long N = 5000010;
const double pi = acos(-1);
long long n,m;
struct owl{
double x,y;
owl operator + (const owl s) const {
return {x + s.x,y + s.y};
}
owl operator - (const owl s) const {
return {x - s.x,y - s.y};
}
owl operator * (const owl s) const {
return {x * s.x - y * s.y,x * s.y + y * s.x};
}
}a[N],b[N];
long long rev[N];
long long bit;
void fft(owl a[],long long op){
for (long long i = 0; i < (1 << bit); i ++ ){
if (i < rev[i]){
swap(a[i],a[rev[i]]);
}
}
for (long long mid = 1; mid < (1 << bit); mid *= 2){
owl w1 = {cos(pi / mid), op * sin(pi / mid)};
for (long long i = 0; i < (1 << bit); i += mid * 2){
owl wk = {1,0};
for (long long j = 0; j < mid; j ++ ,wk = wk * w1){
owl x = a[i + j],y = wk * a[i + j + mid];
a[i + j] = x + y,a[i + j + mid] = x - y;
}
}
}
}
int main(){
string s1,s2;
cin >> s1 >> s2;
n = s1.size() - 1,m = s2.size() - 1;
for (long long i = 0;i <= n; i ++ ){
a[i].x = s1[n - i] - '0';
}
for (long long i = 0; i <= m; i ++ ){
b[i].x = s2[m - i] - '0';
}
while ((1 << bit) < n + m + 1){
bit ++ ;
}
for (long long i = 0; i < (1 << bit); i ++ ){
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
fft(a,1);
fft(b,1);
for (long long i = 0; i < (1 << bit); i ++ ){
a[i] = a[i] * b[i];
}
fft(a,-1);
vector<long long>vec;
long long t = 0;
for (long long i = 0; i < (1 << bit) || t; i ++ ){
t += (long long)(a[i].x / (1 << bit) + 0.5);
vec.push_back(t % 10);
t /= 10;
}
while (vec.back() == 0){
vec.pop_back();
}
for (long long i = vec.size() - 1; i >= 0; i -- ){
cout << vec[i];
}
return 0;
}
在这个数据下:
0
1
应该输出 0,但是以上程序没有输出,但是能AC,建议加强数据。