我绝对不会告诉你我是因为太蒻了，不会 FFT 才搞这个的。
我用一下别人的图没什么问题吧
看得懂吧？比如
X
=
123456
,
Y
=
987654
X=123456,Y=987654
X=123456,Y=987654，则
n
=
3
,
A
=
123
,
B
=
456
,
C
=
987
,
D
=
654
n=3,A=123,B=456,C=987,D=654
n=3,A=123,B=456,C=987,D=654。
前置知识：整数末尾添
0
0
0 方法（不可能不会吧），就是乘
10
10
10，当然添
n
n
n 个零就是乘
1
0
n
10^n
10n，
n
2
\frac{n}{2}
2n 个就是乘
1
0
n
2
10^{\frac{n}{2}}
102n。
失败……
接下来！
∵
X
=
A
×
1
0
n
2
+
B
,
Y
=
C
×
1
0
n
2
+
D
\because X=A imes 10^{\frac{n}{2}} + B,Y=C imes 10^{\frac{n}{2}} + D
∵X=A×102n+B,Y=C×102n+D
∴
X
×
Y
=
(
A
×
1
0
n
2
+
B
)
×
(
C
×
1
0
n
2
+
D
)
=
A
C
×
1
0
n
+
A
D
×
1
0
n
2
+
B
C
×
1
0
n
2
+
B
D
=
A
C
×
1
0
n
+
(
A
D
+
B
C
)
×
1
0
n
2
+
B
D
herefore \begin{align*} X imes Y = &(A imes 10^{\frac{n}{2}} + B) imes (C imes 10^{\frac{n}{2}} + D) \ = &AC imes 10^n + AD imes 10^{\frac{n}{2}} + BC imes 10^{\frac{n}{2}} + BD \ = &AC imes 10^n + (AD+BC) imes 10^{\frac{n}{2}} + BD \end{align*}
∴X×Y===(A×102n+B)×(C×102n+D)AC×10n+AD×102n+BC×102n+BDAC×10n+(AD+BC)×102n+BD
需要进行
4
4
4 次乘法（
1
0
k
10^k
10k 不算，因为是直接添
0
0
0）。
所以时间复杂度
T
(
n
)
=
4
T
(
n
2
)
T(n) = 4T(\frac{n}{2})
T(n)=4T(2n)。
也就是一棵满四叉树，节点数很多，不过只需要关心最后一层。
最后一层有
4
k
4^k
4k 个节点，
k
k
k 为高度（根节点其实为
0
0
0，但是其实都是细节，无伤大雅），
k
=
l
o
g
2
n
k = log_2n
k=log2n。
所以，时间复杂度为
O
(
4
l
o
g
2
n
)
O(4^{log_2n})
O(4log2n)，也就是：
O
(
4
log
2
n
)
=
O
(
(
2
2
)
log
2
n
)
=
O
(
2
2
log
2
n
)
=
O
(
(
2
log
2
n
)
2
)
=
O
(
n
2
)
\begin{align*}\ & O(4^{\log_2n}) \ = & O((2^2)^{\log_2n})\ = & O(2^{2\log_2n})\ = & O((2^{\log_2n})^2) \ = & O(n^2) \end{align*}
====O(4log2n)O((22)log2n)O(22log2n)O((2log2n)2)O(n2)
谔谔，为什么还是
O
(
n
2
)
O(n^2)
O(n2)，这不和原本一样吗ToT。
成功
我们观察式子：
A
C
×
1
0
n
+
(
A
D
+
B
C
)
×
1
0
n
2
+
B
D
AC imes 10^n + (AD+BC) imes 10^{\frac{n}{2}} + BD
AC×10n+(AD+BC)×102n+BD
发现它有三个部分，答案是这三个部分的和：
A
C
×
1
0
n
AC \color{grey}{ imes 10^n}
AC×10n 一次乘法(
A
D
+
B
C
)
×
1
0
n
2
(AD+BC) \color{grey}{ imes 10^{\frac{n}{2}}}
(AD+BC)×102n 两次乘法B
D
×
1
0
0
BD \color{grey}{ imes 10^0}
BD×100 一次乘法
发现就是第二个部分乘法次数最多。
考虑将其优化。
直接优化（化简）：很难，想不出来。
但是，如果式子中用了
A
C
AC
AC 或
B
D
BD
BD，则不会增加乘法次数，因为有重复，可以记录下来。
简单起见，我们关注前半段：
A
D
+
B
C
AD+BC
AD+BC，考虑将其变为
?
?
+
A
C
+
B
D
??+AC+BD
??+AC+BD。
A
D
+
B
C
−
A
C
−
B
D
=
A
(
D
−
C
)
+
B
(
C
−
D
)
=
A
(
D
−
C
)
−
B
(
D
−
C
)
=
(
A
−
B
)
(
D
−
C
)
\begin{align*} \ &AD+BC-AC-BD \ = & A(D-C) + B(C-D) \ = & A(D-C) – B(D-C) \ = & (A-B)(D-C) \end{align*}
===AD+BC−AC−BDA(D−C)+B(C−D)A(D−C)−B(D−C)(A−B)(D−C)
现在，只需要进行一次乘法。最终公式：
A
C
×
1
0
n
+
(
(
A
−
B
)
(
D
−
C
)
+
A
C
+
B
D
)
×
1
0
n
2
+
B
D
AC imes 10^n + ((A-B)(D-C)+AC+BD) imes 10^{\frac{n}{2}} + BD
AC×10n+((A−B)(D−C)+AC+BD)×102n+BD
时间复杂度：
T
(
n
)
=
3
T
(
n
2
)
=
3
log
2
n
=
(
2
log
2
3
)
log
2
n
=
(
2
log
2
n
)
log
2
3
=
n
l
o
g
2
3
\begin{align*} \ T(n)=&3T(\frac{n}{2}) \ =&3^{\log_2n} \ =&(2^{\log_23})^{\log_2n} \ =&(2^{\log_2n})^{\log_23} \ =&n^{log_23} \end{align*}
T(n)=====3T(2n)3log2n(2log23)log2n(2log2n)log23nlog23
那么
log
2
3
\log_23
log23 大约是多少呢？
log
2
3
≈
1.585
\log_23 \approx 1.585
log23≈1.585。
那么到底是多少呢？来不严谨地粗略估计一下：
假设计算机每秒可以执行
1
0
8
10^8
108 条指令。
则最大可以计算的位数为：
n
log
2
3
=
1
0
8
n^{\log_23} = 10^8
nlog23=108，则位数最大约为
111541
111541
111541。
而对比朴素算法
O
(
n
2
)
O(n^2)
O(n2)，最大位数仅为
10000
10000
10000，相比之下多了一个多数量级！
