编写一个程序以从$ f（1）$和$ f（f（1））$找到多项式$ f（x）$

Question

令$ f（x）= a_0+a_1x+a_2x^2+ dots+a_nx^n $，其中$ a_i ge0 $和$ a_i $是整数。

给定$ f（1）= p $和$ f（f（1））= q $，我们必须找到$ a_0 $，$ a_1 $，$ a_2 $，$ a_3 $，$ dots $，$ a_n $ ，存在这样的$ f（x）$的地方。或者我们必须确认是否存在这样的$ f（x）$，或者多项式是否含糊不清，例如$ p = 1 $和$ q = 2 $，不存在这样的$ f（x）$，但对于$ p = 1 $ $ q = 1 $，$ f（x）= 1 $，$ f（x）= x^2 $都可以解决。

我必须编写一个程序才能做到这一点。我的程序应该是什么？

Answer 1

条件$ f（1）= p $和$ f（p）= q $表示以下两个方程：$$ begin {align}＆ sum_ {i = 0}^n a_i = p，＆ sum_ {i = 0}^n a_i p^i = q。 end {align} $$当$ p <0 $或$ p $不是整数时，没有解决方案。当$ p = 0 $时，第一个方程意味着多项式必须为$ 0 $，因此$ q = 0 $。当$ p = 1 $时，方程表示$ p = q $，第一个方程意味着解决方案是多项式$ 1，x， ldots，x^n $。从现在开始，我们假设$ p geq 2 $。

从直观上讲，在上述第二个约束下的多项式最小化$ sum_i a_i $是通过在基本$ p $ notey（第一个$ n $ digits）中编写$ q $来获得的，并将其余作为$ a_n $的系数。用$ b_0， ldots，b_n $表示该解决方案。如果$ sum_i b_i> p $，则没有解决方案。如果$ sum_i b_i = p $，那么我们找到了唯一的解决方案。从现在开始，假设$ sum_i b_i <p $;这意味着$ Q $的基本$ p $扩展最多具有$ n+1 $。

给定的方程式意味着更多的约束。首先，$ q geq p $。其次，由于$ p equiv 1 pmod {p-1} $，我们必须拥有$ q equiv p pmod {p-1} $。从多项式$ g（x）= sum_ {i = 0}^n b_i x^i $开始，我们可以通过应用更新$（b'_ _ {i+1}，b，我们可以增加$ g（1）$ '_i） get（b_ {i+1} - alpha，b_i+p alpha）$（当$ b_ {i+1} geq alpha $时）;这将$ g（1）$增加到$ alpha（p-1）$。我们可以系统地应用这些更新，将质量一直移至多项式$ Q $。由于$ sum_i b_i <p leq q $和$ q equiv p pmod {p-1} $，在此过程中，我们会找到一个（唯一的）多项式满足上述要求的（唯一）。

我们如何以这种过程算法进行操作？我们将索引从$ b_n $到$ b_1 $进行订单。在每个点，我们从$ b_i $中减去最大金额$ alpha $，该$ alpha $保持不变$ g（1） leq p $。处理$ B_1 $之后，我们应该达到所需的多项式。 （我们基本上是在研究$ p -1 $ p -g（1）$的基本$ p -1 $。

Answer 2

如果$ p = 1 $，则约束为$ f（1）= 1 = q $，它可以根据$ q $的值易于解决。现在让我们假设$ p ge 2 $。假设$ f（x）= sum_k a_k x^k $是解决方案。然后$ q = a_0 + a_1 p + a_2 p^2 + ldots + a_n p^n $其中$ n $是$ f $的度（$ a_n ne 0 $）。

对于任何$ k le n $，$ a_k le dfrac {q} {p^k} $。这给出了每个系数的界限。

由于$ p gt 1 $，因此此不限制的$ f $：$ 1 le a_n le le dfrac {q} {p^n} $ so $ n le dfrac { dfrac { log（ log） q）} { log（p）} $。

这表明只有有限数量的候选多项式。然后，您可以列举所有可能的解决方案。首先计算$ f $的最高度$ n $。然后在可能的学位上循环（$ n $至$ 0 $）。对于每个度量$ m $，循环循环$ a_m $的可能值；对于$ a_m $的每个值，请循环循环$ a_ {m-1} $的可能值，依此类推。保持部分总和$ s_k = a_m p^m + ldots + a_k p^k $和$ r_k = a_m + ldots + a_k $;如果这些总和中的任何一个分别超过$ q $或$ p $，请中止树的这一分支。当您到达$ k = 0 $时，$ f $的约束是$ s_1 + a_0 = q $和$ r_1 + a_0 = p $，因此请检查$ s_1 -r_1 -r_1 = q -p $。

我不知道这种方法是否是实用的 - 可能会有更快的算法利用可划分。

Answer 3

您需要一个多项式，以便$ f（1）= p $和$ f（p）= q $。只要$ p neq 1 $，$ p，q> 0 $和$ frac {qp} {p-1}> 0 $（或$ p = q = 1 $）。在所有情况下，多项式$ ax^n+b $就足够了。这里$ p^{n+1}> q $。请注意，没有$ n $太大。