自动搬运

查看原文

来自洛谷，原作者为

	Kinesis **

搬运于2025-08-24 22:03:00，当前版本为作者最后更新于2020-09-05 18:40:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于在模意义下当且仅当$[x^0]f(x) = 1$时，$f(x)$有对数多项式的问题

看到题解有一样和我感到疑惑的谷友：

• $[x^0]f(x) \neq 1$时要怎么求？

貌似也没有大佬给一个比较充分的解释，这里就关于这个问题写~~（水）~~一篇博客吧。

定理：在模意义下当且仅当$[x^0]f(x) = 1$时，$f(x)$有对数多项式。

证明：

根据微积分的基本运算规则，我们可以用求导，再积分的方式求得多项式$f$的对数：$\ln{f(x)} \equiv \int \mathrm{d} \ln f(x) \equiv \int\frac{f'(x)}{f(x)} \mathrm{d} x \pmod{x^{n}},$其中$\int\frac{f'(x)}{f(x)}dx$是$\frac{f'(x)}{f(x)}$的 反导函数，亦称不定积分，其等于$\ln f(x) + c$，$c$为积分常数；由于$\ln f(x)$是已经确定的函数，我们可以确定应用微积分基本定理$\ln f(x) = \int_0^x\frac{f'(t)}{f(t)}dt + \ln f(0)$来确定积分常数$c = \ln f(0)$。

我们知道一个数在$\bmod p$下有意义当且仅当该数是有理数，其表示为$\frac{a}{b},(a,b)=1,$且$(b,p) = 1$。由于采用求导再积分的方式来求多项式$f$的对数，对于$a'_ix^i,i>0$的项数来说，系数均是非负整数，故在模$p,$一般$p = 998244353$下必定是有意义的，故是否存在对数多项式，等价于讨论常数项是否在模p下有意义。

对于多项式$f(x) = \sum\limits_{i=0}^n a_ix^i,f(0) = a_0$，故积分常数为$c = \ln a_0,a_0\in Z$。

此时再给出一个引理：当$a_0 \neq 1$，$\ln a_0 \notin Q,Q$为有理数。证明：式子$c = \ln a_0 \Leftrightarrow a_0 = e^c,$而对于$\forall c \in Q,e^c \notin Q$，由于底数$e$是超越数，故不存在有理数$a_0$使得存在有理数$c$让$e^c$也为有理数，也就是$a_0,c\in Q$时等式不成立。

所谓超越数是相对于代数数来说的。代数数指的是能作为一个整数系数多项式的复根，即当一个数$x_0$为代数数，必存在一个整数多项式$f$满足$f(x_0) = \sum\limits_{i=0}^{n-1}a_ix_0^i = 0$（具体可以看wikipedia-代数数）。而超越数则不能成为任何整数多项式的根。关于自然常数$e$为什么是超越数，链接里有根据采取希尔伯特的策略来证明e是超越数，有基本高数知识就能理解~~（菜鸡笔者理解了一晚上QAQ）~~。

引理的证明：

由于$e$是超越数，故不存在整数多项式$f$使$f(e) = 0$。我们构造一个整数多项式$f(x) = x^n - b_0$，$f(e) = e^n - b_0 \neq 0$，引理得证。故只要$[x^0]f(x) \neq 1$，取对数后就不可能是有理数，也就在模意义下不存在啦~（另外得到了Karry老师的帮助，他是用“当原函数的常数项不等于1，其取对数后不收敛”的用语，可以等价于在模下没有意义）。

故对于多项式$f$，当且仅当$[x^0]f(x) = 1$时有对数多项式$\ln f$；指数多项式亦是同理。