OI-wiki 多项式牛顿迭代法Newtons Method详解从泰勒展开推导到代数完备性证明【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文以 OI-wiki 多项式章节中的 newton.md 为主体系统讲解求解形如 $G(x, f(x))\equiv 0 \pmod{x^{n}}$ 隐式多项式方程的统一算法——多项式牛顿迭代法Newtons Method。作为 多项式初等函数 家族求逆、开方、指数、对数、三角函数等的底层引擎掌握它即可一通百通读完本文你将理解其倍增递推式的来源、迭代格式 $f_{2n}f_n-G(f_n)/G(f_n)$ 的导出过程、三大经典应用多项式求逆、多项式开方、多项式指数函数如何统一在一个框架下并能结合手算演示与抽象代数证明理解算法的可解性条件与解的唯一性。问题描述在形式幂级数环上解方程给定二元多项式 $G(x, y)$已知多项式 $f(x)$ 满足$$ G\left(x, f\left(x\right)\right)\equiv 0\pmod{x^{n}} $$且存在数值 $f_1$ 使 $G(x, y)$ 满足以下条件$G(0, f_1) 0$$\dfrac{\partial G}{\partial y}(0, f_1) \neq 0$目标是求出模 $x^{n}$ 意义下的 $f(x)$。这里的数学背景是 形式幂级数环 $R[[x]]$如 intro.md 所述模 $x^n$ 的操作等价于截断——将无穷项的幂级数截断到前 $n$ 项。因此模 $x^n$ 意义下求解实质上是逐级逼近真实幂级数的过程这为倍增思想提供了天然舞台。初始条件中的 $f_1$ 相当于方程的根而偏导数条件 $\frac{\partial G}{\partial y}(0, f_1) \neq 0$ 保证根是单根简单根这是后续每一步迭代中求逆可进行的必要条件。Newtons Method核心推导考虑倍增策略。初始步当 $n1$ 时$\left[x^{0}\right]G\left(x, f\left(x\right)\right)0$ 的解需要单独求出问题假设中的 $f_1$ 即为一个解。归纳步假设已经得到模 $x^{\left\lceil\frac{n}{2}\right\rceil}$ 意义下的解 $f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$要求模 $x^{n}$ 意义下的解 $f_n\left(x\right)$。将 $G(x, f(x))$ 对 $f(x)$ 在 $f(x)f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$ 处进行泰勒展开$$ \sum_{i0}^{\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}} $$关键的截断观察在于因为 $f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)$ 的最低非零项次数最低为 $\left\lceil\frac{n}{2}\right\rceil$故有$$ \forall 2\leqslant i:\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv 0\pmod{x^{n}} $$也就是说差值的高次幂在模 $x^n$ 意义下全部消失泰勒展开只需保留到一阶项$$ \begin{aligned} \sum_{i0}^{\infty}\frac{\frac{\partial^i G}{\partial y^i}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)^{i}\equiv G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)\left[f\left(x\right)-f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right]\ \equiv 0\pmod{x^{n}} \end{aligned} $$移项整理即得倍增迭代格式$$ f_n\left(x\right)\equiv f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)-\frac{G\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_{\left\lceil\frac{n}{2}\right\rceil}\left(x\right)\right)}\pmod{x^{n}} $$或者写成更便于实现的精度翻倍形式从 $n$ 位翻倍到 $2n$ 位$$ f_{2n}\left(x\right)\equiv f_n\left(x\right)-\frac{G\left(x, f_n\left(x\right)\right)}{\frac{\partial G}{\partial y}\left(x, f_n\left(x\right)\right)}\pmod{x^{2n}} $$这与实数的 牛顿迭代法 $x_{i1}x_i-\frac{f(x_i)}{f(x_i)}$ 在形式上完全同构在实数域上迭代收敛位数翻倍平方收敛在形式幂级数环上则表现为精度位数翻倍——每次迭代把已知解从模 $x^n$ 提升到模 $x^{2n}$因而总复杂度满足 $T(n)T(n/2)O(n\log n)$。例题三大初等函数如何统一进牛顿框架多项式求逆参见 elementary-func.md#多项式求逆。设给定函数为 $h(x)$构造$$ G\left(x, y\right)\frac{1}{y}-h\left(x\right) $$此时 $\frac{\partial G}{\partial y}-\frac{1}{y^2}$。应用 Newtons Method$$ \begin{aligned} f_{2n}\left(x\right)\equiv f_{n}\left(x\right)-\frac{1/f_{n}\left(x\right)-h\left(x\right)}{-1/f_{n}^{2}\left(x\right)}\pmod{x^{2n}}\ \equiv 2f_{n}\left(x\right)-f_{n}^{2}\left(x\right)h\left(x\right)\pmod{x^{2n}} \end{aligned} $$这就是广为人知的求逆倍增公式 $f_{2n}f_n(2-f_nh)$。仓库中 elementary-func.md 给出的polyinv实现正是这一格式的直接编码void polyinv(const poly h, const int n, poly f) { /* f 1 / h f_0 (2 - f_0 h) */ static poly_t inv_t; std::fill(f, f n n, 0); f[0] fpow(h[0], mod - 2); for (int t 2; t n; t 1) { const int t2 t 1; std::copy(h, h t, inv_t); std::fill(inv_t t, inv_t t2, 0); DFT(f, t2); DFT(inv_t, t2); for (int i 0; i ! t2; i) f[i] (i64)f[i] * sub(2, (i64)f[i] * inv_t[i] % mod) % mod; IDFT(f, t2); std::fill(f t, f t2, 0); } }注意初始化f[0] fpow(h[0], mod - 2)正是牛顿法单独解出 $n1$ 时的初始解这一步——求逆的常数项即 $h$ 常数项的乘法逆元这也印证了 intro.md 中存在倒数当且仅当常数项不为 $0$的结论。时间复杂度$$ T\left(n\right)T\left(\frac{n}{2}\right)O\left(n\log{n}\right)O\left(n\log{n}\right) $$多项式开方参见 elementary-func.md#多项式开方。设给定函数为 $h(x)$构造$$ G\left(x, y\right)y^{2}-h\left(x\right)\equiv 0 $$此时 $\frac{\partial G}{\partial y}2y$。应用 Newtons Method$$ \begin{aligned} f_{2n}\left(x\right)\equiv f_{n}\left(x\right)-\frac{f_{n}^{2}\left(x\right)-h\left(x\right)}{2f_{n}\left(x\right)}\pmod{x^{2n}}\ \equiv\frac{f_{n}^{2}\left(x\right)h\left(x\right)}{2f_{n}\left(x\right)}\pmod{x^{2n}} \end{aligned} $$仓库中多项式开方的完整可运行参考代码位于 docs/math/code/poly/sqrt/sqrt_1.cpp洛谷 P5205 模板题其核心倍增部分与上面的公式一一对应void sqrt(int deg, int *f, int *h) { if (deg 1) { h[0] 1; return; } sqrt((deg 1) 1, f, h); int len 1; while (len deg * 2) { // 倍增 len * 2; } fill(g, g len, 0); inv(deg, h, g); // 先求 h 的逆 copy(f, f deg, t); fill(t deg, t len, 0); NTT(t, len, 1); NTT(g, len, 1); NTT(h, len, 1); for (int i 0; i len; i) { h[i] (long long)1 * inv2 * ((long long)1 * h[i] % mod (long long)1 * g[i] * t[i] % mod) % mod; } NTT(h, len, -1); fill(h deg, h len, 0); }这段代码展示了牛顿迭代的完整工程细节递归求解模 $x^{\lceil \deg/2\rceil}$ 的解作为本轮输入对应 $f_n$通过inv求 $f_n$ 的逆元对应 $1/(2f_n)$ 中的 $1/f_n$再用 NTT 点值相乘实现 $f_n^2(x)h(x)$ 与 $f_n^{-1}(x)$ 的卷积对应 $\frac{f_n^2h}{2f_n}$最后乘上 $2^{-1}\mathrm{inv2}$。整体乘法均基于模 $998244353$ 的 NTT 完成ntt_1.cpp 提供了该 NTT 的完整实现。关于开方的可解性elementary-func.md#多项式开方 还补充了细节常数项 $\left[x^0\right]f(x)\sqrt{\left[x^0\right]g(x)}$ 必须存在平方根可能需要二次剩余且上述方法需要 $f_0(x)$ 可逆故常数项不能为 $0$若 $\left[x^0\right]g(x)0$则需分解 $g(x)x^{k}h(x)$$k$ 为奇数时无平方根$k$ 为偶数时开 $h(x)$ 再整体乘 $x^{k/2}$。时间复杂度$$ T\left(n\right)T\left(\frac{n}{2}\right)O\left(n\log{n}\right)O\left(n\log{n}\right) $$多项式指数函数参见 elementary-func.md#多项式对数函数--指数函数。设给定函数为 $h(x)$构造$$ G\left(x, y\right)\ln{y}-h\left(x\right) $$此时 $\frac{\partial G}{\partial y}\frac{1}{y}$。应用 Newtons Method$$ \begin{aligned} f_{2n}\left(x\right)\equiv f_{n}\left(x\right)-\frac{\ln{f_{n}\left(x\right)}-h\left(x\right)}{1/f_{n}\left(x\right)}\pmod{x^{2n}}\ \equiv f_{n}\left(x\right)\left(1-\ln{f_{n}\left(x\right)}h\left(x\right)\right)\pmod{x^{2n}} \end{aligned} $$注意这里要求 $[x^0]h(x)0$否则 $\exp$ 的常数项不收敛而 $[x^0]f_n(x)1$这样 $f_n$ 可逆且 $\ln f_n$ 有意义。仓库中 elementary-func.md 的polyexp实现正是此公式的编码其中每轮迭代内部都要调用一次polyln它又依赖polyinv——这体现了牛顿迭代框架的分层嵌套特征指数函数依赖对数函数与求逆求逆又依赖 NTT构成了完整的多项式算法栈。时间复杂度$$ T\left(n\right)T\left(\frac{n}{2}\right)O\left(n\log{n}\right)O\left(n\log{n}\right) $$注三个例题的时间复杂度形式完全相同均为 $O(n\log n)$。这与每次迭代精度翻倍、单次迭代代价为 $O(n\log n)$ 的卷积这一结构完全匹配。作为对比elementary-func.md 中提到若不使用牛顿法而用分治 FFT 直接解 $\exp$ 的系数递推复杂度为 $O(n\log^2 n)$可见牛顿法的效率优势。手算演示把算法跑在纸面上为了直观理解倍增流程下面用两组例子逐步演示。复数多项式模多项式的平方根假设 $h$ 是一个不被 $x$ 整除有常数项的复数多项式求它对模 $x^n$ 的平方根。方程$$ G\left(f(x)\right) f^2(x)-h(x) \equiv 0\pmod{x^{n}} $$对 $G$ 作泰勒展开注意这里是对 $f$ 展开导数都是对 $f$ 的偏导数$x$ 当作常数处理$$ G(f(x)) \sum_{i0}^{\infty}\frac{G^{\left(i\right)}\left(f_{0}(x)\right)}{i!}\left(f(x)-f_{0}(x)\right)^{i} G(f_0(x)) 2f_0(x)(f(x)-f_0(x)) (f(x)-f_0(x))^2 $$用倍增计算。设倍增中的中间结果是 $f_0(x), f_1(x), \ldots, f_j(x)$严谨地说 $f_j(x)$ 是满足 $G(f_j(x))\equiv 0\pmod{x^{2^j}}$ 的复数多项式且为了唯一性同时满足$f_{j}(x)$ 的次数不超过 $2^j-1$即只保留模 $x^{2^j}$ 内的项$f_{jk}(x)-f_j(x)\equiv 0\pmod{x^{2^j}}$对所有 $k$后续项在低精度下与当前解一致。把 $f_{j1}(x)$ 和 $f_j(x)$ 代入展开式$$ G(f_{j1}(x)) G(f_j(x)) 2f_j(f_{j1}(x)-f_j(x)) (f_{j1}(x)-f_{j}(x))^2 \equiv 0 \pmod{x^{2^{j1}}} $$由于 $f_{j1}(x)-f_j(x)$ 必然是 $x^{2^j}$ 的倍数其平方被 $x^{2^{j1}}$ 整除于是$$ f_{j1}(x) \equiv f_j(x) - \frac{f_j^2(x)-h(x)}{2f_j(x)} \equiv \frac{f_j(x)^2 h(x)}{2f_j(x)} \pmod{x^{2^{j1}}} $$可解性分析若 $f_j(x)$ 存在那么 $2f_j(x)$ 不被 $x$ 整除有常数项故必然有模 $x^{2^{j1}}$ 的逆元下一步迭代总能进行。因此数列 $f_0,f_1,\ldots,f_j$ 存在当且仅当 $f_0$ 存在。而不被 $x$ 整除的复数多项式 $h(x)$ 模 $x$ 的平方根一定存在$h(x)$ 模掉 $x$ 就是一个普通非零复数一定有两个平方根。所以对所有有常数项的 $h(x)$ 该算法都适用。选 $h(x)x1$ 实际计算取 $f_0(x)1$$f_1(x)\dfrac{1^2x1}{2\times 1}\mod x^2 \dfrac{1}{2}x1$$f_2(x)\dfrac{\left(\frac{1}{2}x1\right)^2x1}{2\times \left(\frac{1}{2}x1\right)}\mod x^4 \dfrac{1}{16}x^3-\dfrac{1}{8}x^2\dfrac{1}{2}x1$$\ldots$取 $f_0(x)-1$$f_1(x)\dfrac{(-1)^2x1}{2\times (-1)}\mod x^2 -\dfrac{1}{2}x-1$$\ldots$结果恰为前一条取负可以验证两条都是正确的模平方根多项式列——这正对应平方根的双值性$\pm$ 两个分支。整数模素数幂的平方根牛顿迭代算法还可迁移到整数模素数幂的情形。假设 $h$ 是一个不被 $3$ 整除的整数求 $h$ 在模 $3^n$ 意义下的平方根 $f$不被 $3$ 整除保证初始根存在具体条件后文再言。方程$$ G\left(f\right) f^2-h \equiv 0\pmod{3^{n}} $$泰勒展开$$ G(f) \sum_{i0}^{\infty}\frac{G^{\left(i\right)}\left(f_{0}\right)}{i!}\left(f-f_{0}\right)^{i} G(f_0) 2f_0(f-f_0) (f-f_0)^2 $$倍增计算设中间结果是 $f_0, f_1, \ldots, f_j$其中 $f_j$ 满足 $G(f_j)\equiv 0\pmod{3^{2^j}}$且$0 f_{j} 3^{2^j}$$f_{jk}-f_j\equiv 0\pmod{3^{2^j}}$对所有 $k$。代入后由于 $f_{j1}-f_j$ 是 $3^{2^j}$ 的倍数其平方被 $3^{2^{j1}}$ 整除$$ G(f_{j1}) G(f_j) 2f_j(f_{j1}-f_j) (f_{j1}-f_{j})^2 \equiv 0 \pmod{3^{2^{j1}}} $$得$$ f_{j1} \equiv f_j - \frac{f_j^2-h}{2f_j} \equiv \frac{f_j^2 h}{2f_j} \pmod{3^{2^{j1}}} $$可解性分析若 $f_j$ 存在则 $2f_j$ 不被 $3$ 整除故有模 $3^{2^{j1}}$ 的逆元迭代总可继续。因此数列存在当且仅当 $f_0$ 存在。而不被 $3$ 整除的整数 $h$ 模 $3$ 的平方根要么不存在要么有两个。所以$h$ 有模 $3$ 的平方根就是整个算法能跑的唯一条件。选 $h46$ 实际计算取 $f_01$$f_1\dfrac{1^246}{2\times 1}\mod 9 1$$f_2\dfrac{1^246}{2\times 1}\mod 81 64$$f_3\dfrac{64^246}{2\times 64}\mod 6561 955$$\ldots$取 $f_02$$f_1\dfrac{2^246}{2\times 2}\mod 9 8$$f_2\dfrac{8^246}{2\times 8}\mod 81 17$$f_3\dfrac{17^246}{2\times 17}\mod 6561 5606$$\ldots$等于前一条取负可以验证两条都是正确的模平方根数列模 $3^n$ 意义下 $955 \equiv -5606 \pmod{6561}$ 成立。这一节说明牛顿迭代法并非只服务于多项式在 $\mathbb Z/p^n\mathbb Z$ 这类环上同样成立其本质是局部环上的亨泽尔引理Hensels lemma式提升这与代数证明部分的抽象化表述是同一思想。代数证明为什么一定存在解以及为什么能得到全部解前面各节用微积分语言完成了推导与验证本节用抽象代数的语言把结论一般化并严格化。前提概念整环、唯一分解整环、形式幂级数环可参考 抽象代数基本概念。有解的证明引理 1单根提升引理设整环 $R$ 有多项式或形式幂级数 $f(X) \sum_{i\geq 0}a_iX^i$以及 $r,p\in R$ 使得 $f(r)\in Rp$即 $r$ 是 $f(X)$ 在模 $p$ 意义下的根且 $f(r)\in R$ 在模 $p$ 意义下可逆。这里 $f(X) : \sum_{i\geq 0}(i1)a_{i1}X^i$ 是 $f(X)$ 的形式导数。那么$$ f\left(r-\dfrac{f(r)}{f(r)}\right) \equiv 0\pmod {p^2} $$证明对所有 $s\in R$ 展开 $f(rsp)$$$ \begin{aligned} f(rsp) \sum_{i\geq 0}a_i(rsp)^i \ \sum_{i\geq 0}a_ir^i sp\sum_{i\geq 1}ia_ir^{i-1} s^2p^2\left(\ldots\right) \ f(r) spf(r) s^2p^2\left(\frac{f(r)}{2!} \cdots\right), \end{aligned} $$所以 $f(rsp) \in Rp^2 \iff f(r)f(r)sp \in Rp^2$。因为 $f(r)\in Rp$ 且 $f(r)$ 可逆取 $sp -\dfrac{f(r)}{f(r)}$ 即可其中 $\dfrac{1}{f(r)}$ 是模 $p^2$ 意义下的逆元。$f(r)$ 在模 $p$ 意义下可逆保证了它在模 $p^2$ 意义下也存在逆元设有 $a,b,c\in R$ 使 $af(r) bp1$ 和 $f(r)cp$那么 $\left(a^2f(r)-2\right)f(r) b^2p^21$故可取 $sc(2-a^2f(r))$。∎对于域 $k$ 上的多项式环 $k[X]$设 $G(X, Y)\in k[X, Y]$ 和 $f_n\in k[X]$ 使 $G(X, f_n(X))\in k[X]X^n$应用引理 1取 $pX^n$$rf_n$即得$$ G\left(X, f_n(X) - \frac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))} \right)\equiv 0 \pmod {X^{2n}} $$这正是牛顿迭代一步把精度从 $n$ 提到 $2n$ 的代数版本。归纳启动倍增的初始条件只需有 $f_1\in k$ 使得 $G(X, f_1)\equiv 0\pmod X$ 且 $\dfrac{\partial G}{\partial Y}(X, f_1)\not\equiv 0\pmod X$。后一个条件保证了 $\dfrac{\partial G}{\partial Y}$ 有非零常数项又因为 $X$ 整除 $\dfrac{G(X, f_n(X))}{\frac{\partial G}{\partial Y}(X, f_n(X))}$分子被 $X^n$ 整除、分母常数项非零故而对所有的 $n$$\dfrac{\partial G}{\partial Y}(X, f_n)$ 总是模 $X^n$ 意义下可逆的满足了下一次迭代的条件。于是由归纳法只要初始单根条件成立牛顿法对所有 $n$ 都能给出模 $X^n$ 意义下的解。得到全部解的证明引理 2唯一性引理若 $R$ 为 唯一分解整环$f,r,p$ 定义同引理 1则引理 1 给出的 $r-\dfrac{f(r)}{f(r)}$ 是模 $p^{2}$ 意义下唯一满足以下两条件的 $x$$f(x)\in Rp^{2}$$x-r\in Rp$。亦即$$ \forall x\in R,\qquad p^2\mid f(x)\wedge p\mid (x-r) \implies x\equiv r-\dfrac{f(r)}{f(r)} \pmod {p^2} $$证明令 $s -\dfrac{f(r)}{f(r)p}$$u rsp$。引理 1 保证 $u$ 满足两个条件且 $f(r) f(r)sp \in Rp^{2}$。设 $v$ 是任一满足上述条件的值则有 $v rtp$ 和 $f(r) f(r)tp \in Rp^{2}$。两式相减得 $f(r)(t-s)p\in Rp^{2}$由于 $f(r)$ 可逆故 $v-u\in Rp^{2}$唯一性得证。∎完备性论证牛顿法可以保证得到模 $X^{2^n}$ 的全部解。假设 $G(X, h)\equiv 0\pmod {X^{2^n}}$令 $h_{2^i} : h\pmod {X^{2^i}}$取 $f_1 h_1$ 并用牛顿法根据引理 2 可得 $f_{2^i} \equiv h_{2^i}\pmod {X^{2^i}}$ 对每个 $i$ 成立所以一定有 $f_{2^n} h$。也就是说任意模 $X^{2^n}$ 的解都可以由牛顿法从模 $X$ 的解出发重建出来。推论上面的论证还说明在 $\dfrac{\partial G}{\partial y}(0, y)$ 永远可逆时$G(X, f)\equiv 0\pmod {X^n}$ 的解的个数等于 $G(0, f)\equiv 0\pmod X$ 的解的个数——即高精度下的解完全由低精度常数项下的解决定。这个结论并非平凡看下面的反例牛顿法无效时解的个数随次数变多的例子模 $X$ 意义下 $X^2$ 的平方根只有 $0$但是模 $X^4$ 意义下 $X^2$ 的平方根有 $X, -X, X^3X, \ldots$。此处 $G(X,Y)Y^2-X^2$ 在 $Y0$ 处的偏导 $\frac{\partial G}{\partial Y}2Y$ 恒为零重根牛顿法条件 $\frac{\partial G}{\partial y}\neq 0$ 被破坏于是每提升一次精度解就分叉的现象出现解的个数不再守恒。这个例子从反面凸显了单根条件偏导数非零是牛顿法良好行为存在性 完备性的关键前提。小结牛顿法的使用要点要点说明适用对象形如 $G(x, f(x))\equiv 0\pmod{x^n}$ 的隐式多项式方程初始条件需先求 $n1$ 时的解 $f_1$且 $\frac{\partial G}{\partial y}(0,f_1)\neq 0$单根迭代格式$f_{2n}\equiv f_n-\dfrac{G(x,f_n)}{\partial G/\partial y,(x,f_n)}\pmod{x^{2n}}$关键前提每步迭代要求 $f_n$ 可逆或分母 $\frac{\partial G}{\partial y}(x,f_n)$ 可逆复杂度$T(n)T(n/2)O(n\log n)O(n\log n)$解的结构单根条件下模 $x^n$ 的解与模 $x$ 的解一一对应且可被牛顿法全部重建反例警示若 $\frac{\partial G}{\partial y}$ 在根处为 $0$重根解可能随精度增长而分叉延伸阅读多项式与生成函数形式幂级数环、乘法逆元、模 $x^n$ 截断等前置概念多项式初等函数求逆、开方、除法、取模、$\ln$/$\exp$、三角/反三角函数的完整解法与代码快速数论变换 NTT 与 参考实现牛顿迭代每轮所需的卷积底层多项式开方参考实现可运行的洛谷 P5205 模板题完整代码抽象代数基本概念整环、UFD、形式幂级数环的定义与性质数值牛顿迭代法实数域上的牛顿法及平方根求解与本文的环上版本互为对照【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考