# 博客

## HALF-GCD 算法的阐述

2020-03-10 17:48:53 By EntropyIncreaser

There is a way to calculate the GCD and resultants in $O(n\log^2n)$. To do this you should note that if you consider $a(x)=a_0+x^ka_1$ and $b(x)=b_0+x^kb_1$ where $k=\min(\deg a,\deg b)/2$ then basically the first few operations of Euclidean algorithm on $a(x)$ and $b(x)$ are defined by the Euclidean algorithm on $a_1(x)$ and $b_1(x)$ for which you may also calculate GCD recursively and then somehow memorize linear transforms you made with them and apply it to $a(x)$ and $b(x)$ to lower the degrees of polynomials. Implementation of this algorithm seems pretty tedious and technical thus it's not considered in this article yet.

## 评论

englandmen
sto EntropyIncreaser
luosiyuan
sto EntropyIncreaser
laosb
sto EntropyIncreaser