首页
IT
登录
6mi
u
盘
搜
搜 索
IT
【51nod1028】【大数乘法 V2】【fft】
【51nod1028】【大数乘法 V2】【fft】
xiaoxiao
2021-12-15
35
题目大意
给出2个大整数A,B,计算A*B的结果。
解题思路
fft,然而会卡精度,使用模运算的fft即可解决问题。
code
#include<cmath>
#include<cstdio>
#include<algorithm>
#define LD double
#define LL long long
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int
const maxn=
1
e5,g=
3
,mo=
1004535809
;
int
n,
m
,A,B,w[maxn
*4
+
10
],a[maxn
*4
+
10
],b[maxn
*4
+
10
],t[maxn
*4
+
10
]; void
read
(
int
&num,
int
*a
){ num=
0
;
int
v=
0
;char ch=getchar();
for
(;(ch<
'0'
)||(ch>
'9'
);ch=getchar());
for
(;(ch>=
'0'
)&&(ch<=
'9'
);a[num++]=ch-
'0'
,ch=getchar());
int
mx=num/
2
-
1
;fo(i,
0
,mx)swap(a[i],a[num-i-
1
]); }
int
up(LD
x
){
return
int
(
x
)+((
int
(
x
)==
x
)?
0
:
1
);} void DFT(
int
*a
,
int
tag){ fo(i,
0
,n-
1
){
int
pos
=
0
;
for
(
int
j=
0
,ii=i;j<
m
;
pos
=(
pos
<<
1
)+(ii&
1
),ii=ii>>
1
,j++); t[
pos
]=a[i]; }
for
(
int
i=
2
;i<=n;i=i<<
1
){
int
half=i>>
1
; fo(j,
0
,half-
1
){
int
wi=(tag>
0
)?w[n/i
*j
]:w[n-n/i
*j
];
for
(
int
k=j;k<n;k+=i){
int
x
=t[k],
y
=
1
ll
*wi
*t
[k+half]
%mo
; t[k]=(
x
+
y
)
%mo
; t[k+half]=(
x
-
y
+mo)
%mo
; } } } fo(i,
0
,n-
1
)a[i]=t[i]; }
int
Pow(
int
x
,
int
y
){
int
z=
1
;
while
(
y
){
if
(
y
&
1
)z=
1
ll
*z
*x
%mo
;
x
=
1
ll
*x
*x
%mo
;
y
=
y
>>
1
; }
return
z; }
int
main(){ freopen(
"d.in"
,
"r"
,stdin); freopen(
"d.out"
,
"w"
,stdout);
read
(A,a);
read
(B,b);
m
=up(
log
(max(A,B)<<
1
)/
log
(
2
));n=
1
<<
m
; w[
0
]=
1
;w[
1
]=Pow(g,(mo-
1
)/n); fo(i,
2
,n)w[i]=
1
ll
*w
[i-
1
]
*w
[
1
]
%mo
; DFT(a,
1
);DFT(b,
1
); fo(i,
0
,n-
1
)a[i]=
1
ll
*a
[i]
*b
[i]
%mo
; DFT(a,-
1
);
int
ni=Pow(n,mo-
2
); fo(i,
0
,n-
1
)a[i]=
1
ll
*a
[i]
*ni
%mo
; fo(i,
0
,n-
1
){ a[i+
1
]+=a[i]/
10
; a[i]
%=
10
; }
for
(;a[n]==
0
;n--); fd(i,n,
0
)putchar(a[i]+
'0'
);
return
0
; }
转载请注明原文地址: https://ju.6miu.com/read-1000039.html
专利
最新回复
(
0
)