刚学OI萌新求助多项式开根

P5205 【模板】多项式开根

@[_venti](/user/1033727) 可以,但只能算常数为 1 的情况。常数非 1 的话需要除成 1 最后再乘上这个数的二次剩余
by Imiya @ 2024-01-24 08:33:28


@[Faccirx](/user/206052) 诶原来这东西可以套到多项式上面的吗?但是在模 $P-1(=998244352)$ 的意义下 $2$ 没有逆元,也就是说 $\frac{1}{2}$ 模不了 $P-1(=998244352)$!
by _venti @ 2024-01-24 08:44:27


@[Imiya](/user/455558) 诶等一下,突然想到一个问题,$F^{\frac{1}{2}\mod P}(x)$ 的平方是 $F^{P+1}(x)$,但是 $F^{k\mod P}(x)$ 会等于 $F^k(x)$ 吗?
by _venti @ 2024-01-24 08:50:26


@[_venti](/user/1033727) 在取 $\ln$ 取 $\exp$ 那种快速幂里,指数是模 $P$ 意义下的。所以是。
by Imiya @ 2024-01-24 09:57:51


@[Imiya](/user/455558) 谢谢,我试一下...
by _venti @ 2024-01-24 10:10:00


@[Imiya](/user/455558) www成功了 [~~前来还愿~~](https://www.luogu.com.cn/record/145214376)
by _venti @ 2024-01-30 16:33:38


|