Problem. S

题意简述:

给定复数(z=sumlimits_{i=1}^nz_i(z_iinmathbb Z[i])),求(mathbb K[mathbb Z[i]])上的使得(f(z)=0)的多项式(f(z))的最低次数,答案对(998244353)取模。

数据范围:

(nle100,|z_i|le10^9)

解法:

(p(x))(z)(mathbb Z)上的极小多项式,那么(deg p=[mathbb Z(a):mathbb Z])
(a_i)两两互质,则显然有([mathbb Z(sqrt a_1,cdots,sqrt a_n):mathbb Z]=2^n)
(p^2|a_i),那么(p|sqrt a_iwedge pinmathbb Z),因此我们可以将(a_i)的因子中所有的(p^2)去掉,这并不会影响答案。
对于每个(a_i)构造一个向量(mathbf b_i),满足(mathbf b_{i,j}=p_j|a_i)
(mathbb F_2)(operatorname{span}(mathbf b_1,cdots,mathbf b_n)=m),那么([mathbb Z(sqrt a_1,cdots,sqrt a_n):mathbb Z]=2^m)
(a=sumlimits_{i=1}^na_i),又因为(p(a)=p(overline a)=0),所以我们有([mathbb Z(a):mathbb Z]=[mathbb Z(sqrt a_1,cdots,sqrt a_n):mathbb Z]=2^m)
我们知道(mathbb Z[i])上是有唯一分解定理的,因此可以套用(mathbb Z)上的做法。
总的时间复杂度为(O(frac{n^3log|z|}{omega}+nsqrt{|z|}))

原文地址:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12958250.html